KMP算法
在字符串匹配中，我们一般是BF算法，暴力破解。当然上完数据结构课之后，我们知道可以通过KMP进行优化。
上数据结构这门课的时候，我没有好好听KMP，本篇文章参考程杰老师的《大话数据结构》中KMP算法一章节记录的笔记，可以的话请阅读原书中该章节，这里相当于原书的复述。
这边引用书中的一句话：任何有难度的知识和技巧，都不是那么容易掌握的。我尽管已经朝着通俗易懂的方向努力，可有些数据结构，特别是经典算法，是几代科学家的智慧结晶，因此要掌握他们还是需要读者的全力投入。
1.Next串
关于Next串，根据Pattern串进行得出的回溯串。
案例1
1）Next数组，第一位Next[1]=0
2）j=2的时候，j从0到j-1就只有字符“a“，那么给定一个1
3）j=3的时候，j从0到j-1就只有字符“ab"，那么给定一个1
往后同理
案例2
1）Next数组，第一位Next[1]=0
2）j=2的时候，同上，Next[2]=1
3）j=3的时候，同上，Next[3]=1
4）j=4的时候，同上，Next[4]=1
5）j=5的时候，此时j由1到j-1的串是“abca”，前缀“a”，后缀“a”，推算k的值为2，则Next[5]=2
6）j=6的时候，串为“abcab”，前缀“a”，后缀“a”，我们可以回溯到3，Next[6]=3
我们可以根据经验得到如果前后缀一个字符相等，k的值是2，两个字符k的值是3，第n个就是n+1
案例3
1）Next数组，第一位Next[1]=0
2）j=2的时候，同上，Next[2]=1
3）j=3的时候，同上，Next[3]=1
4）j=4的时候，串为“aba”，前缀“a”，后缀“a”，则Next[4]=2
5）j=5的时候，串为“abab”，前缀“ab”，后缀“ab”，则Next[5]=3
6）j=6的时候，串为“ababa”，前缀“aba”，后缀“aba”，则Next[6]=4
7）j=7的时候，串为“ababaa”，只有“a”符合，则Next[7]=2
8）j=8的时候，串为“ababaaa”，只有“a”符合，则Next[8]=2
9）j=9的时候，串为“ababaaab”，只有”ab“符合，则Next[9]=3
案例4
1）Next数组，第一位Next[1]=0
2）j=2的时候，同上，Next[2]=1
3）j=3的时候，前缀为“aa”与后缀“aa”相同，Next[3]=2
4）j=4的时候，前缀为“aaa”与后缀“aaa”相同，Next[4]=3
.....
2.朴素KMP
通过这么多，我们可以来看一下代码，下面是朴素next数组和KMP，我们这边next是朴素KMP的求解方案
void get_next(string T, int *next) { // T是匹配串
int i = 1, j = 0;
next[1] = 0;
while(i < T[0]){// T[0]存储T的长度
if(j == 0 || T[i] == T[j]) {
i++;
j++;
next[i] = j;
}else {
j = next[j]; // 回溯
}
}
}
int KMP(string S, string T, int pos){
int i = pos, j = 1;
int next[255];
get_next(T, next);
while(i <= S[0] && j <= T[0]){
if(j == 0 || S[i] == T[j]){
i++;
j++;
}else j = next[j];
}
if(j > T[0]) return i - T[0];
else return 0;
}
3.KMP算法改进
朴素KMP存在一些缺陷。例如：S="aaaabcde"，子串 T = "aaaaax"分别是012345，在开始，我们发现b与a不相等，因此j=next[5]=4，紧接着回溯3，直到0。所以我们在算法改进中进行优化操作，若与之前相等，则进行与之前相等操作。
void get_next(string T, int *next) { // T是匹配串
int i = 1, j = 0;
next[1] = 0;
while(i < T[0]){// T[0]存储T的长度
if(j == 0 || T[i] == T[j]) {
i++;
j++;
if(T[i] != T[j]) // 如果与前缀字符串不一样
next[i] = j; // 进行设置j为i
else
next[i] = next[j]; // 否则进行赋值操作
}else {
j = next[j]; // 回溯
}
}
}
4.nextval数组改进推导
案例
1）开始nextval[1] = 0
2）第二位字符b的nextval为1，二第一位就是“a”，不相等，维持原值
3）第三位字符a的nextval为1，“a”与“a”相等，则变换为0
4）第四位字符b的nextval为2，“b”与“b”相等，则变换为1
5.总结
其实只要细心耐心，KMP算法理解后也不是想象中那么麻烦，写起来还蛮方便的。但是在算法调试中，KMP确实不太好写，我们记忆住原理优先。