1.KMP算法

1.1 簡介

研究的是子串（必須連續）。

int getIndexOf(String str1,String str2);

用的就是KMP算法，不在時返回-1；在時返回在原串中的位置。

時間復雜度是，最起碼得遍歷完原串。

最壞情況，時間復雜度為.

KMP算法：讓前面配過的元素指導后面的匹配，這樣就可以加速匹配。

1.2?最長前綴和最長后綴之間的匹配長度

一個字符之前的那個字符串的最長前綴和最長后綴之間的匹配長度（前綴不能包含最后一個字符，后綴也不能包含最前的一個字符）。

1.2.1 舉例1

上題中：

• 長度取1：a≠c
• 長度取2：ab≠bc
• 長度取3：abc=abc
• 長度取4：abca≠cabc
• 長度取5：abcab不等于bcabc
• 長度只能取到5

所以答案為3.

1.2.2 舉例2

此題中，答案是4

1.2.3 引到next數組

對字符串中的每一位進行計算，得到一個next數組：

1.3 KMP過程

下面，開始用str2的這個next數組進行KMP的過程解釋。

假設現在從str1的i位置開始h和str2的0位置開始匹配：

一路都匹配，直到x和y不匹配。

1.3.1 暴力方法

從str1的i+1位置開始，繼續和str2的0位置開始匹配。

1.3.2 改進方法

依據y位置的next值，進行加速處理。

假設Y位置的最長前綴和最長后綴的長度如圖所示：

將str2中的后綴對應到str1中對應的位置，如下圖：

假設str1中相對應的位置起始為j位置，那么接下來就是str1的j位置和str2的0位置開始往后匹配，如下圖;

由于str2中前綴標出的部分和后綴中標出的部分是相匹配的，所以str2中前綴的部分和str1中從j位置開始的等長部分也匹配。所以，現在實際上開始匹配的位置是str1中的j位置和str2中的k位置，即比較x和z是否匹配。如圖：

1.3.3 舉例1

1.3.3 推兩次舉例

第一次：i是str1中的圖中開始的a的位置；j是第一次推之后str1中和str2中0位置比較的位置；

第二次：i是第一次的j，j是第二次推之后，str1中和str2中0位置比較的位置。

第一次看F的next，決定str2推的位置，D和a沒匹配上；

此時看a的next決定第二次往后退的位置，2個。比較D和k。沒匹配上；

k位置的next為0，所以下一步就是D之后的字符和str2的0位置元素開始匹配。

1.3.4 推的過程的實質

第一次匹配完之后，甲在t位置，乙在F位置，然后甲不動，乙跳到str2中的5位置（即，乙跳到str2中的next[F]的位置），繼續和甲指向的元素t進行匹配。

1.3.5 具體匹配過程

甲指向的字符和乙指向的字符相等：甲++；乙++；

若不相等：

乙指向字符對應的next為-1，則說明是str2的起始位置，甲++（即，甲指向的str1中的字符和str2中0位置的字符都不匹配，那就是str1后一個字符繼續和str2中0位置的字符比較）；

否則，乙跳到str2中的next[乙]的位置。

若循環完之后，乙位置超過了str2，則說明匹配成功，返回甲-乙（目前匹配到的位置-乙=str2在str1中的位置）；否則返回-1，即不存在。

1.4 next數組的求解

0位置為-1，1位置為0，2位置（若0位置和1位置的字符相等則為1，否則為0）。

其他位置：數學歸納法

目前要求i位置的next值。已知i-1位置的next值為4。則，若前綴串的后一個字符x=b（i-1位置的字符），則i位置的next值為4+1=5。

如果不等：

則看前綴后面的字符x的next值，劃分出它的前綴和后綴，然后看x的最長前綴之后的字符和b（i-1位置的字符）是否相等，相等則i位置的next值為x的next值+1，否則繼續分。一直到沒得分，則i位置的next值才為0；

1.4.1 舉例1

1.4.2 舉例2

將1.4.1中的i-1位置換為a：

1.2 代碼實現

package Classics;public class KMP {public static void main(String[] args) {String str = "abcabcababaccc";String match = "ababa";System.out.println(getIndexOf(str, match));}public static int getIndexOf(String str1,String str2) {if(str1==null||str2==null)return -1;int i1=0;int i2=0;int[] next=getNextArray(str2);char[] chs1=str1.toCharArray();char[] chs2=str2.toCharArray();while(i1<chs1.length&&i2<chs2.length) {if(chs1[i1]==chs2[i2]) {i1++;i2++;}else if(next[i2]>-1){i2=next[i2];//回退}else {//i2在str2的0位置，則需要i1的下一個位置來和str2的0位置（i2位置）匹配i1++;}}return i2==str2.length()?i1-i2:-1;}public static int[] getNextArray(String str2) {if(str2.length()==1)return new int[] {-1};char[] chs=str2.toCharArray();int[] next=new int[chs.length];next[0]=-1;next[1]=0;int i=2;int cn=0;while(i<chs.length) {if(chs[i-1]==chs[cn]) {//x和b相等，則i位置的next值=i-1的next值+1；next[i++]=++cn;}else if(next[cn]>0){cn=next[cn];}else {next[i++]=0;}}return next;} }

?

總結

以上是生活随笔為你收集整理的算法练习day16——190404（KMP算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。