kmp.jpg
kmp算法最主要的是计算出next数组
[0,0,1,2,0,1,2,3,1]
len:表示next[i]处的值
next数组主要是如果新加入的字符和pattern[len]不相同是该怎么算len=next[len-1] 回退到next[len-1] 对应字符的next的值
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 pattern){
char patterns[]=pattern.toCharArray();
int[] next = new int[pattern.length()];
next[0] = 0;
int len=0;
int i=1;
while (i<next.length) {
if (patterns[i]==patterns[len]) {
len++;
next[i]=len;
i++;
}else{
if (len>0) {
len=next[len-1];
}else{
next[i]=0;
i++;
}
}
}
return next;
}
public static void main(String[] args){
String a = "ababa";
String b = "ssdfgasdbababa";
int[] next = kmpnext(a);
for(int i = 0; i < next.length; i++){
System.out.print(next[i] +" ");
}
int res = kmp(b, a,next);
System.out.println(res);
System.out.println(next.length);
}
}
