目的：
为了解决字符串模式匹配
历程：
朴素模式匹配：逐次进行比较
KMP算法：利用匹配失败得到的信息，来最大限度的移动模式串，以此来减少比较次数提高性能
概念：
m：是目标串长度
n：是模式串长度
j：某次匹配时，第一次出现的不同的索引位置（有的称为：失配位）
k：最长首尾串长度（有的称为：最长公共前后缀）
核心思想：
S S0 S1 ...... Si-j-1 Si-j Si-j+1 Si-j+2 ...... Si-2 Si-1 Si ...... Sn-1
|| || || || || ×
P P0 P1 P2 Pj-2 Pj-1 Pj
有Si-j-1Si-jSi-j+1 Si-j+2 ...... Si-2 Si-1=P0P1 P2 ...... Pj-2 Pj-1
如果 P0P1 P2 ...... Pj-2 ≠ P1 P2 ...... Pj-2Pj-1
则可以立即断定 P0P1 P2 ...... Pj-2 ≠ Si-j+1 Si-j+2 ...... Si-2 Si-1，即：朴素模式匹配的下一次移动一定不匹配，则可以跳过这一次
如果 P0P1 P2 ...... Pj-3 ≠ P2 ...... Pj-2Pj-1
则可以立即断定 P0P1 P2 ...... Pj-2 ≠ Si-j+1 Si-j+2 ...... Si-2 Si-1，即：朴素模式匹配的下一次移动一定不匹配，则可以跳过这一次
直到第一次出现相等的情况终止：P0P1 P2 ...... Pk-1 = Pj-k ...... Pj-2Pj-1
得到的k就是最长的首尾串长度，然后通过 j-k 得到了我们需要移动的位数，这样我们就利用了匹配失败的结果，得到了我们可以移动的步数，提升了性能
关于k：
其实肉眼就直接能看出来，k是最长首尾串长度，比如：
11111 k=4（前缀：1111，后缀：1111）
12112 k=2（前缀：12，后缀：12）
12345 k=0（无相同前缀后缀）
例子：
S=ababababababb
P=abababb
重申一下原理：朴素模式匹配效率低的原因是一位一位的比较，丢弃了之前失败的信息。而KMP算法从匹配失败的信息中得到可以最大移动的步数，以此来减少比较的次数，来提升性能。
这里并没有提及，next数组及newnext数组，模式串的特征向量N，其实不用管它，思想理解了，只是别人起了个叫法而已。
Java代码：
/**
* 朴素模式匹配
*
* @param source 目标串
* @param pattern 模式串
*/
private static void plain(String source, String pattern) {
int res=0;
int sourceLength=source.length();
int patternLength=pattern.length();
for(int i=0;i<=(sourceLength-patternLength);i++){
res++;
String str=source.substring(i, i+patternLength);
if(str.equals(pattern)){
p("朴素模式：匹配成功");
break;
}
}
p("朴素模式：一共匹配"+res+"次数");
}
//KMP算法实现
private static void KMP(String source, String pattern) {
int[] N=getN(pattern);
int res=0;
int sourceLength=source.length();
int patternLength=pattern.length();
for(int i=0;i<=(sourceLength-patternLength);){
res++;
String str=source.substring(i, i+patternLength);//要比较的字符串
p(str);
int count=getNext(pattern, str,N);
p("移动"+count+"步");
if(count==0){
p("KMP：匹配成功");
break;
}
i=i+count;
}
p("KMP：一共匹配"+res+"次数");
}
/**
* 得到下一次要移动的次数
*
* @param pattern
* @param str
* @param N
* @return 0,字符串匹配；
*/
private static int getNext(String pattern,String str,int[] N) {
int n = pattern.length();
char v1[] = str.toCharArray();
char v2[] = pattern.toCharArray();
int x = 0;
while (n-- != 0) {
if (v1[x] != v2[x]){
if(x==0){
return 1;//如果第一个不相同，移动1步
}
return x-N[x-1];//x:第一次出现不同的索引的位置，即j
}
x++;
}
return 0;
}
private static int[] getN(String pattern) {
char[] pat=pattern.toCharArray();
int j=pattern.length()-1;
int[] N=new int[j+1];
for(int i=j;i>=2;i--){
N[i-1]=getK(i,pat);
}
for(int a:N)
p(a);
return N;
}
private static int getK(int j, char[] pat) {
int x=j-2;
int y=1;
while (x>=0 && compare(pat, 0, x, y, j-1)) {
x--;
y++;
}
return x+1;
}
private static boolean compare(char[] pat,int b1,int e1,int b2,int e2){
int n = e1-b1+1;
while (n-- != 0) {
if (pat[b1] != pat[b2]){
return true;
}
b1++;
b2++;
}
return false;
}
public static void p(Object obj) {
System.out.println(obj);
}
next数组：
KMP能提高性能原因是减少了比较次数，也就是知道k
而k从只和j有关，这就意味着移动的次数只和模式串有关，和目标串无关
简单来说，就是我们得到模式串后就能立马知道移动的次数，这就是next数组。里面储存的就是k值。