KMP算法简介就不讲了，对于朴素的模式串匹配算法，发生失配时每次只能移动一个位置，然后再进行比较，而KMP算法可以根据模式串本身的性质，来决定向后跳几步
下面我们用一个例子来说明
next数组的计算公式是
其实next数组还有一个简单的方法可以看出来
就是看它前面的与第0位开始的重复多少个，比如上面的 j=2的时候 next[1]=0,且p[j-1]=b!=p[0]，所以next[j]=0;
当j=3时，其前面的为a==p[0]所以next[j]=1;
下面模拟下KMP算法的过程
第一趟
j=1的时候发生失配，next[j]=next[1]=0,所以要从p0重新开始匹配
第二趟
| a | c | a | b | a | a | b | a | a | b | c | a | c | a | a | b | c |
| a | b | a | a | b | c | a | c |
第三趟
| a | c | a | b | a | a | b | a | a | b | c | a | c | a | a | b | c |
| a | b | a | a | b | c | a | c |
j=5的时候发生失配，next[j]=next[5]=2,说明前面有两个是有p0p1重复的，目标串在这之前都是匹配的，所以说明目标串前面的两个也一定是与p0p1重复的，所以可以从p2匹配起
第四趟
| a | c | a | b | a | a | b | a | a | b | c | a | c | a | a | b | c |
| a | b | a | a | b | c | a | c |
匹配成功。
下面提供一下产生next数组的代码
java版本的
public static int[] makenext(String s){
int[] next=new int[s.length()];
next[0]=-1;
if(next[1]==next[0]) next[1]=1;
else next[1]=0;
for(int i=2;i<s.length();i++){
if(s.charAt(i-1)==s.charAt(next[i-1])) next[i]=next[i-1]+1;//这步是关键就是判断前面的一位是否满足重复序列
else {
if(s.charAt(i-1)==s.charAt(0)) next[i]=1;
else next[i]=0;
}
}
return next;
}
根据上面演示的KMP的过程，也可以得出下面的代码
public static void main(String[] args) {
// TODO Auto-generated method stub
String pattern="cacaa";
String target="acabaabaabcacaabc";
int[]next=makenext(pattern);
int i=0;
int j=0;
boolean flag=false;
while(true) {
if(i>=target.length()) break;
if(j==pattern.length()) {
flag=true;
break;
}
if(target.charAt(i)==pattern.charAt(j)) {
i++;
j++;
} else {
if(j>0) {
j=next[j];
} else {
i++;
j=0;
}
}
}
if(flag) {
for(int k=0;k<pattern.length();k++)
System.out.print(target.charAt(k+i-j));
}
else System.out.println("没有匹配到");
}