KMP是解決兩個字符串匹配問題的非常好的算法撒轮，算法的時間復(fù)雜是O(n)产捞。
現(xiàn)在假設(shè)場景是兩個字符串str1醇锚，str2，求str2是否是str1的子串坯临，如果是焊唬，返回第一個子串的第一個字母在str1中的索引。
例如：str1 = "ababcababtk";str2 = "ababtk";則返回5看靠。
要使用KMP算法赶促，首先要算出用來加速匹配的str2的數(shù)組next；
一挟炬、next數(shù)組的求解
next[n]中裝的是str2中索引為n的字符前面的子串substr2前綴與后綴相等的最長前綴的長度鸥滨，前綴與后綴的要求是，前綴一定要包含子串substr2的第一個字符谤祖，但是不能包含最后一個字符婿滓，后綴一定要包含子串substr2的最后一個字符，但是不能包含最后一個字符粥喜。
比如對于字符串str2中的't'前面的子串就是abab凸主，它的前綴是"a","ab","aba"；后綴是"b","ab","bab"额湘。前綴與后綴相等的最長前綴的長度是2卿吐，所以't'對應(yīng)的next數(shù)組的值是2，即next[4] = 2锋华。
規(guī)定next[0] = -1,next[1] = 0,這是人為規(guī)定的嗡官，當(dāng)然如果str2的長度為1，那么next數(shù)組就只有一個-1供置。
下面介紹怎么利用前面的next值求后面的next的值谨湘。
假設(shè)str中n-1位置求出的最長相等前后綴長度是m，要求n位置的最長相等前后綴長度即next[n]芥丧，下面為了方便表述紧阔，將str字符串看成一個str字符數(shù)組。
1续担、str[n-1] = str[m],如下圖擅耽，n-1和m的位置都是'k'，所以'b'對應(yīng)的next[n] = m+1;
2物遇、str[n-1] != str[m],如下圖乖仇，則看字符't'對應(yīng)的next[m],假設(shè)next[m] = u,如果next[u]=next[m],則'b'對應(yīng)的next[n] = u+1,否則再看next[u],按照上述步驟繼續(xù)進(jìn)行憾儒，直到next[x] = -1為止，此時next[n] = 0;
使用上述方法求出的str2的next數(shù)組是[-1,0,0,1,2,0]乃沙。
public static int[] getNext(String str){
// 如果str長度為1起趾，直接返回只含-1的數(shù)組
if(str.length() == 1){
return new int[]{-1};
}
int[] next = new int[str.length()];
char[] str2 = str.toCharArray();
// 首先將人為設(shè)定最長相等前綴的值填好
next[0] = -1;
next[1] = 0;
int n = 2;
// m代表i前面一個字符的最長相等前綴的長度，最開始i=2,next[i-1] = 0,所以n的初始值是0警儒；
int m = 0;
while(n < next.length){
// 這是情況一训裆，str[n-1] = str[m],此時next[n] = m+1
if(str2[m] == str2[n-1]){
next[n++] = ++m;
// 這是情況二，str[n-1] != str[m],此時蜀铲，m = next[m],再次比較
}else if(m > 0){
m = next[m];
// 當(dāng)m=0時,則next[n] = 0;
}else{
next[n++] = 0;
}
}
return next;
}
二边琉、使用next數(shù)組加速匹配
還是上述問題，str1 = "ababcababtk"记劝；str2 = "ababtk"变姨，上面已經(jīng)求出str2的next數(shù)組是[-1,0,0,1,2,0]，p1是指向str1當(dāng)前匹配位置的指針厌丑，p2是指向str2當(dāng)前位置的指針定欧，開始匹配時會出現(xiàn)下面的情況。為了方便描述蹄衷，還是將str1和str2看成兩個字符數(shù)組忧额。
1、str1[p1] == str2[p2] 愧口，則p1和p2都往后移一位。
2类茂、str1[p1] != str2[p2]且p2 != 0耍属，則p2 = next[p2]，p1不動巩检。
3厚骗、str1[p1] != str2[p2]且p2==0，p2不移動兢哭，p1向后移動一位领舰。
如果p2 = str2.length，停止上述過程迟螺，此時子串的第一個字符在str1中的位置是p1-p2冲秽，否則直到str1遍歷完，之后若p2 != str2.length矩父，則str1中不包含str2锉桑，否則子串的第一個字符在str1中的位置是p1-p2。
完整代碼實現(xiàn)如下：
public static void main(String[] args) {
String str1 = "ababcababtk";
String str2 = "ababtk";
int[] next = getNext(str2);
int res = KMP(str1,str2,next);
System.out.println(res);
}
public static int KMP(String str1,String str2,int[] next){
if(str1 == null || str2 == null || str2.length() < 1 || str1.length() < str2.length()){
return -1;
}
char[] strArr1 = str1.toCharArray();
char[] strArr2 = str2.toCharArray();
int p1 = 0;
int p2 = 0;
while(p1 < strArr1.length && p2 < strArr2.length){
// 情況1窍株，strArr1[p1] == strArr2[p2] 民轴，則p1和p2都往后移一位
if(strArr1[p1] == strArr2[p2]){
p1++;
p2++;
// 情況3攻柠，str1[p1] != str2[p2]且p2==0，p2不移動后裸，p1向后移動一位
}else if(p2 == 0){
p1++;
// 情況2瑰钮，str1[p1] != str2[p2]且p2!=0，則p2 = next[p2]微驶，p1不動飞涂。
}else{
p2 = next[p2];
}
}
return p2 == strArr2.length ? p1-p2:-1;
}
public static int[] getNext(String str){
// 如果str長度為1，直接返回只含-1的數(shù)組
if(str.length() == 1){
return new int[]{-1};
}
int[] next = new int[str.length()];
char[] str2 = str.toCharArray();
// 首先將人為設(shè)定最長相等前綴的值填好
next[0] = -1;
next[1] = 0;
int n = 2;
// m代表i前面一個字符的最長相等前綴的長度祈搜，最開始i=2,next[i-1] = 0,所以n的初始值是0较店；
int m = 0;
while(n < next.length){
// 這是情況一，str[n-1] = str[m],此時next[n] = m+1
if(str2[m] == str2[n-1]){
next[n++] = ++m;
// 這是情況二容燕，str[n-1] != str[m],此時梁呈，m = next[m],再次比較
}else if(m > 0){
m = next[m];
// 當(dāng)m=0時,則next[n] = 0;
}else{
next[n++] = 0;
}
}
return next;
}
