KMP 算法基本原理
KMP 算法是根据三位作者（D.E.Knuth，J.H.Morris 和 V.R.Pratt）的名字来命名的，算法的全称是 Knuth Morris Pratt 算法，简称为 KMP 算法。
KMP 算法的核心思想是：我们假设主串是 a，模式串是 b。在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，我们希望找到一些规律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况。
第一次匹配的情况如图
当i = 6的时候，匹配失败，说明前面的都能匹配上，我们希望找到x前缀和后缀相同的位置，这样我们就能快速的将j定位到c
从上图我们可以看出，这个过程跳过了很多多余的比较，那我们怎么呢做呢？
事实上，KMP 算法也可以提前构建一个数组，用来存储模式串中每个前缀的最长可匹配前缀子串的结尾字符下标。我们把这个数组定义为next 数组，很多书中还给这个数组起了一个名字，叫失效函数（failure function）。简单的说就是回溯的位置。
next数组的计算方法
next函数的计算方法是KMP最绕的部分
在求解next数组的4种情况:
- 默认next[1] = 0;
- 当 i=0时,表示当前的比应该从头开始.则i++,j++,next[j] = i;
- 当 T[i] == T[j] 表示2个字符相等,则i++,j++.同时 next[j] = i; 也就是说下一个字符的应该回溯的位置是i;
- 当 T[i] != T[j]` 表示不相等,则需要将i 退回到合理的位置. 则 i = next[i];
T[i] != T[j] 进行回退. [i,j]范围有没有前缀和后缀;
[next[i],j] 范围有没有前缀和后缀;（扩大范围）
最终直到[0,j]范围有没有前缀和后缀;
此时next为01112
我用C写了一份next的求解代码
//----KMP 模式匹配算法---
//1.通过计算返回子串T的next数组;
//注意字符串T[0]中是存储的字符串长度; 真正的字符内容从T[1]开始;
//很多书中还给这个数组起了一个名字，叫失效函数（failure function）。next函数求解也是kmp中最绕的部分
void get_next(String T,int *next) {
int i = 0;
int j = 1;
next[1] = 0;
while (j<T[0]) {
if (i==0 || T[i] == T[j]) {
i++;
j++;
next[j] = i; //匹配相同说明前面的字符匹配，成功那么下一个字符的回溯位置就是i,这里的特殊在于当我们要计算 next[j] 的时候，前面的 next[0]，next[1]，……，next[j-1] 应该已经计算出来了
} else {
//如果字符不相同,则i值回溯;
i = next[i];
}
}
}
有了next数组，我们接下来实现KMP算法
思路：
- 遍历模式串S,i 是用来标记主串的索引; 遍历模式串, j 是用来标记模式串的索引;
- 结束条件是当i > S.length 和 j > T.length;
如果 i > S.length 但是j 却小于T.length 表示遍历了整个主串,都没有找到与模
式串匹配的情况
只有1种可能,就是j > T.length 表示,已经在主串中找到模式串了. 因为你已经顺
利的把T模式串中的每个字符串正常的依次比较下去了,直到它结束; - 当 j = 0 时,表示此时你需要将模式串从1这个位置与主串i+1这个位置开始比较;
- 当 T[i] == T[j], 表示此时当前模式串j 与 主串i 这个2个字符是相等,则j++,i++;
- 当 j != 0 并且T[i] != T[j] 时,表示此时需要移动模式串的 j ,那么我们让 j =
next[j]; 来节省重复的比较次数;
//KMP 匹配算法(1)
//返回子串T在主串S中第pos个字符之后的位置, 如不存在则返回0;
int Index_KMP(String S,String T,int pos){
int i = pos;
int j = 1;
int next[MAXSIZE];
get_next(T, next);
while (i <= S[0] && j <= T[0]) {
//j==0，第一个就不匹配
if (j == 0 || S[i] == T[j]) {
//匹配成功i和j同时后移
i++;
j++;
} else {
//回溯,如果不匹配时,j回退到合适的位置,i值不变;
j = next[j];
}
}
if (j>T[0]) {
return i-T[0];//i全部匹配完成的下标，要减去T的长度
}
return -1;
}
这部分很简单，其实就是字符匹配成功，i和j同时后移，如果匹配不成功，j回溯到合适的位置也就是当前next[j]的值，继续进行匹配。
循环结束，当j大于T的长度，说明匹配成功，否则匹配失败。
失效函数优化
此时的next为01234
当i == 5时，可以模拟一下，这里又有很多重复比较，j从4一直回溯到0，此时i = 6 ，j = 1，继续比较. 你又没有发现：4到1的这部分比较其实是多余。那么我们要nextval为00004,也就是说我们x不匹配的时候j回溯到4，此时T[4]为a,同样不匹配，那么j回溯到0，此时i++,j++，也就是开始比较主串的下一个字符
那么如何实现呢？
在求解nextVal数组的5种情况:
- 默认next[1] = 0;
- T[i] == T[j] 且++i,++j 后 T[i] 依旧等于 T[j] 则 nextval[i] = nextval[j]
- i = 0, 表示从头开始i++,j++后,且T[i] != T[j] 则nextVal = j;
- T[i] == T[j] 且++i,++j 后 T[i] != T[j] ,则nextVal = j;
- 当 T[i] != T[j]` 表示不相等,则需要将i 退回到合理的位置. 则 i = next[i];
//KMP 匹配算法(2)next数组优化
//求模式串T的next函数值修正值并存入nextval数组中;
void get_nextVal(String T,int *nextVal){
int i = 0;
int j = 1;
nextVal[1] = 0;
while (j<T[0]) {
if (i==0 || T[i] == T[j]) {
i++;
j++;
//如果当前字符与前缀不同,则当前的j为nextVal 在i的位置的值
if (T[i] != T[j]) {
nextVal[j] = i;
} else {
//如果当前字符相等并且前缀相同,则将前缀的nextVal 值赋值给nextVal 在i的位置，也就是说，让当前j应该回溯的位置和i相同
nextVal[j] = nextVal[i];
}
} else {
//如果字符不相同,则i值回溯;
i = nextVal[i];
}
}
}
