例一：
先看看next数据值的求解方法
| 位序 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 模式串 | a | b | a | a | b | c | a | b | c |
| next值 | 0 | 1 | 1 | 2 | 2 | 3 | 1 | 2 | 3 |
next数组的求解方法是：
1.第一位的next值为0
2.第二位的next值为1
后面求解每一位的next值时，根据前一位进行比较
3.第三位的next值：第二位的模式串为b ,对应的next值为1;将第二位的模式串b与第一位的模式串a进行比较，不相等；则第三位的next值为1(其他情况均为1)
4.第四位的next值：第三位的模式串为a ,对应的next值为1;将第三位的模式串a与第一位的模式串a进行比较，相同，则第四位的next值得为1+1=2
5.第五位的next值：第四位的模式串为a，对应的next值为2;将第四位的模式串a与第二位的模式串b进行比较，不相等；第二位的b对应的next值为1,则将第四位的模式串a与第一位的模式串a进行比较，相同，则第五位的next的值为1+1=2
6.第六位的next值：第五位的模式串为b，对应的next值为2;将第五位的模式串b与第二位的模式中b进行比较，相同，则第六位的next值为2+1=3
7.第七位的next值：第六位的模式串为c，对应的next值为3;将第六位的模式串c与第三位的模式串a进行比较，不相等；第三位的a对应的next值为1，
则将第六位的模式串c与第一位的模式串a进行比较，不相同，则第七位的next值为1(其他情况)
8.第八位的next值：第七位的模式串为a，对应的next值为1;将第七位的模式串a与第一位的模式串a进行比较，相同，则第八位的next值为1+1=2
9.第八位的next值：第八位的模式串为b，对应的next值为2;将第八位的模式串b与第二位的模式串b进行比较，相同，则第九位的next值为2+1=3
如果位数更多，依次类推
例二：在例一中，每次不相等时返回的都是k=next[k]=0，都是返回到了开头，我们看一个不是返回到开头0的情况：
| 序号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 子串 | a | a | b | c | a | a | a | b | a | a | c |
| Next值 | -1 | 0 | 1 | 0 | 0 | 1 | 2 | 2 | 3 | 1 | 2 |
从 j=5，k=1的时候开始
5，比较 S[1] == S[5] 所以 j++，k++，next[j+1=6]=k=2
6，比较S[2] != S[6] 所以 k返回到next[k=2]位置，即k=next[2]=1,然后比较S[k=1] == S[6] 所以 j++ ，k=1+1=2，next[7]=k=2
…………
因此，我们发现K的退回 是退回到next[k]的位置 即S[j]!=S[k]时，k=next[k]
public class KMP {
public static int kmp(String str, String dest,int[] next){//str文本串 dest 模式串
for(int i = 0, j = 0; i < str.length(); i++){
while(j > 0 && str.charAt(i) != dest.charAt(j)){
j = next[j - 1];
}
if(str.charAt(i) == dest.charAt(j)){
j++;
}
if(j == dest.length()){
return i-j+1;
}
}
return 0;
}
public static int[] kmpnext(String dest){
int[] next = new int[dest.length()];
next[0] = 0;
for(int i = 1,j = 0; i < dest.length(); i++){
while(j > 0 && dest.charAt(j) != dest.charAt(i)){
j = next[j - 1];
}
if(dest.charAt(i) == dest.charAt(j)){
j++;
}
next[i] = j;
}
return next;
}
public static void main(String[] args){
String a = "ababa";
String b = "ssdfgasdbababa";
int[] next = kmpnext(a);
int res = kmp(b, a,next);
System.out.println(res);
for(int i = 0; i < next.length; i++){
System.out.println(next[i]);
}
System.out.println(next.length);
}
}
