今天看了kmp算法，最開始看得特別混亂，最后終于看明白了，想記錄一下。
https://github.com/hym105289/KMP/blob/master/src/KMP.java
1.題目
給定兩個字符串str和match，長度分別為N和M。實現(xiàn)一個算法，如果字符串str中含有子串match，則返回match在str中開始的位置，不含有則返回-1.
2.暴力解法
一般匹配字符串時，我們從目標字符串str（假設長度為n）的第一個下標選取和match長度（長度為m）一樣的子字符串進行比較，如果一樣，就返回開始處的下標值，不一樣，選取str下一個下標，同樣選取長度為n的字符串進行比較，直到str的末尾（實際比較時，下標移動到n-m）。這樣的時間復雜度是O(n*m)。
public static int search(String str,String match){
int N=str.length();
int M=match.length();
for (int i = 0; i <= N-M; i++) {
int j=0;
for (j = 0; j < M; j++) {
if (str.charAt(i+j) != match.charAt(j)) {
break;
}
}
if (j == M) {
return i;
}
}
return -1;
}
回溯i指針
public static int search3(String pat, String txt) {
int j, M = pat.length();
int i, N = txt.length();
for (i = 0, j = 0; i < N && j < M; i++) {
if (txt.charAt(i) == pat.charAt(j))
j++;
else {
i -= j;
j = 0;
}
}
if (j == M)
return i - M; // found
else
return N; // not found
}
3.KMP
看一下暴力比較壞的情況
KMP改進的地方：每當一趟匹配過程中出現(xiàn)字符串不等時，利用已經(jīng)得到的部分比較結(jié)果，將模式向右滑動盡可能多的距離。
比如在上述的圖片中i=6，j=5時不匹配，我們根據(jù)之間的匹配結(jié)果，可以直接將i=6和模板j=0處進行比較，而無需將i進行回溯。
關鍵問題：當主串中的第i個字符和模式串中的第j字符不匹配時，主串中的i字符應該和模式串中的哪個字符再比較？
假設此時的主串中的i字符串和模式串中的k字符進行比較，必須滿足以下兩個條件：
①已經(jīng)得到的匹配結(jié)果：
②主串i能和模式串k進行比較：
由①和②可以推斷出：
這三個式子說明的問題：
當主串S[i]!=P[j]的時候，主串i和模式串j不匹配時，主串i將和模式串k比較中的k的值，其實是取決于模式串本身的特性，與主串無關。
①求解KMP算法的第一步，就是要求出當主串和模式串j不匹配時，主串應該繼續(xù)和模式串中的哪個字符進行比較。計算模式字符串match的nextArr數(shù)組。
前綴子串：以第一個字符開始，連續(xù)但是不包括最后一個字符的字符串；
后綴子串：不能以第一個字符開始，連續(xù)但必須包括最后一個字符的字符串；
nextArr[j]:就是求從模式字符串下標從0到j的字符串的前綴子串和后綴子串的最大匹配長度。
eg：模式串match=abaabcac,模式串的長度為8:
nextArr[0]：計算match[0]之前的字符串=空，前綴子串和后綴子串的最大匹配長度=0——nextArr[0]=-1(第一個字符在它之前沒有字符規(guī)定設置為-1)；
nextArr[1]：計算match[1]之前的字符串=a，前綴子串和后綴子串的最大匹配長度=0——nextArr[1]=0；
nextArr[2]：計算match[2]之前的字符串=ab，前綴子串和后綴子串的最大匹配長度=0——nextArr[2]=0；
nextArr[3]：計算match[3]之前的字符串=aba，前綴子串a(chǎn)和后綴子串a(chǎn)的最大匹配長度=1——nextArr[3]=1；
nextArr[4]：計算match[4]之前的字符串=abaa，前綴子串a(chǎn)和后綴子串a(chǎn)的最大匹配長度=1——nextArr[4]=1；
nextArr[5]：計算match[5]之前的字符串=abaab，前綴子串a(chǎn)b和后綴子串a(chǎn)b的最大匹配長度=1——nextArr[5]=2；
nextArr[6]：計算match[6]之前的字符串=abaabc，前綴子串和后綴子串的最大匹配長度=0——nextArr[6]=0；
nextArr[7]：計算match[7]之前的字符串=abaabca，前綴子串a(chǎn)和后綴子串a(chǎn)的最大匹配長度1——nextArr[7]=1；
②假設我們已經(jīng)求出啊來了nextArr數(shù)組，利用兩個指針si和pi分別指向查找字符串和模式字符串的首字符，如果匹配成功，則si++，pi++，如果匹配不成功，并且是在第一個模式串字符處匹配不成功，則si++，其他位置匹配不成功，si處的字符和next[pi]的模式串字符進行匹配；這個過程最多執(zhí)行N次，時間復雜度為O(n).
public static int getIndex(String str, String pat){
if (str == null || pat == null || str.length() <pat.length() || pat.length() <1) {
return -1;
}
char[] s=str.toCharArray();
char[] p=pat.toCharArray();
int si=0,pi=0;
int[] next=getNextArr(p);
while (si<s.length&&pi<p.length) {
if(s[si] == p[pi]){//字符串匹配則兩個指針不斷向前移動
si++;
pi++;
}
else if (next[pi] == -1) {//和模式字符串的第一個字符不匹配，則指向s的字符串向前移動
si++;
}else {
pi=next[pi]; //匹配失敗，則重新定位模式串的該匹配字符
}
}
return pi == p.length ? si-pi:-1;
}
如何快速得到模式字符串pat的nextArr數(shù)組，并且復雜度是O(m)？
pat=abaabcac
1.對于nextArr[0]而言，由于它之前沒有字符，所以規(guī)定nextArr[0]=-1;
2.對于nextArr[1]而言，由于它之前只有一個字符，所以一定沒有匹配的前綴子串和后綴子串，nextArr[1]=0；
3.當下標pos>1時求解過程如下：
①從左到右依次求解nextArr數(shù)組，先求nextArr[0],nextArr[1],nextArr[2]....最后求nextArr[m-1]，這說明當我們求nextArr[i]時，其實nextArr[i-1]已經(jīng)求好了，我們已經(jīng)知道B處之前字符串的前綴子串和后綴子串的最大匹配區(qū)域。
②如果字符C和字符B相等，那么A之前的最長前綴子串和后綴子串匹配的區(qū)域就可以確定了，nextArr[i]=nextArr[i-1]+1;
③如果字符C！=字符B，就看字符C之前的前綴和后綴的匹配區(qū)域。
m區(qū)域和n區(qū)域分別是字符C之前的字符串的最長匹配的后綴與前綴區(qū)域，這是通過next[cn]確定的，我們可以根據(jù)圖示看到相同顏色的代表匹配的字符串，那么一定可以在字符B之前的最長匹配的后綴字符串中找到和m區(qū)域相同長度的m'區(qū)域。，接下來比較字符D和字符B是否相同？
1）D==B，nextArr[i]=nextArr[cn]+1;
2 ) D != B,繼續(xù)往前跳到字符D，然后重復類似的過程，每次跳一步都會有一個新的字符和B進行比較，如果相等，則nextArr[i]就能夠確定。
④ 如果向前跳到最左的位置，即pat[0]的位置，nextArr[0]==-1,則說明字符A之前的字符不存在匹配的前綴和后綴子串，nextArr[i]=0；
public static int[] getNextArray(char[] pat){
if (pat.length==1) {
return new int[]{-1};
}
int[] next=new int[pat.length];
next[0]=-1;
next[1]=0;
int pos=2;
int cn=0;//注意cn總是記錄著next[pos-1]的值
while (pos<next.length) {
if (pat[pos-1]==pat[cn]) {
next[pos++]=++cn;
}else if (cn>0) {
cn=next[cn];
}else {
next[pos++]=0;
}
}
return next;
}
