KMP算法应该算是我学习程序开发以来第一个真正独立学习理解的算法，看了许多网络上的视频和文字教程依旧很难彻底掌握（尤其是next数组的计算过程），所以我将我对于该算法的主观认识记录于此。
BF
Brute-Force(BF) 算法又称naive算法，是对字符串子串搜索最简单明了的算法。其主旨就是：
- 不处理模式串
- 模式串从目标串第一个元素起逐一匹配
- 发现无法匹配，模式串匹配右移一位，从下一位目标串元素重新初始逐一元素匹配
虽然简单易懂，但是同时也导致了复杂度较高，最慢的情形其复杂度可以到达O（模式串长 * 目标串长）。
KMP
但是如果仔细观察，可以发现模式串本身是可以自带一些可被预先计算出的可用于加速匹配的信息的。
当模式串的第K位失配时，前K-1位必然是匹配的，如果直接整体后移一位重新从头开始匹配那之前的那些已经匹配的信息就被浪费了。于是我们可以寻找最大的必定不需要再匹配的串，那这个串是什么呢？
很显然，这个串就是[1,K-1]位串中最大且相同的头尾串（S）。当失配发生，可以直接保持目标串中的失配元素不变，移动模式串，K-1-S串长个单位重新匹配，这就是KMP算法。
为什么要移动K-1-S串长个单位？失配元素前方一共有K-1个元素，最大相同头尾串长为S。
若移动小于K-1-S长度(例如K-1-S-1 = K - 1 - (S+1))，则必然无法匹配，因为不存在更大的相同首尾串，如下图中（bab不是相同首尾串，故必然不匹配）。
若移动大于K-1-S长度(例如K-1-S+1 = K - 1 - (S-1))，有可能匹配（当S-1同样是相同子串时），但是可能会因为多移动了位数而遗漏结果。
KMP算法本身比较好理解，而关于KMP的实现需要引入一个Next数组（由模式串预处理出的数组），Next数组的本身的算法则很难理解。
Next数组
Next数组的含义很直观，就是第几个元素失配时应该右移模式串重新匹配第几个元素（不同的教材采用的首元素索引序号不同有的是0有的是1，这也是Next数组算法难以理解的一大原因，所以文中讨论索引序号都直接使用的是第几个元素）。
Next数组的算法步骤如下图所示，在我们逐步讨论完其算法过程后再会看这张动图或许你会有更深刻地理解。
逐步讨论
对于模式串的首个元素的Next值，约定为首元素索引值 - 1，这么做仅仅是为了方便实现递归算法。这个值不一定只为首元素的Next值，经过优化后可能为其他元素的Next值，这个值（首元素索引 - 1）的含义是：
将模式串的首元素移动到失配元素后一位并从首元素开始，重新匹配。
ababdababab
第一步：初始化首元素的Next值。
第二步：讨论第一个元素的Next值，从而决定第二个元素的Next值。发现第二个元素无法匹配时，前方并不存在免匹配元素（不存在相同的首尾串），故值为首元素索引。
第三步：讨论第二个元素的Next值，从而决定第三个元素的Next值。发现第三个元素无法匹配时，第二个元素无法通过它自身的Next值对应的元素（索引为1的元素a）以及如此递归，构成相同首尾的串。因此第三个元素前方不存在相同首尾串，因此其Next值为首元素索引。
第四步：讨论第三个元素的Next值，从而决定第四个元素的Next值。发现第四个元素无法匹配时，第三个元素（a）与其Next值（1）对应的元素（a）（第一个元素）相同，因此第三个元素必定在一个具有相同首尾的串的尾串中，并且扮演最尾元素的角色，其串长为0（首元素的Next值为0，在这里阻止递归，约定其串长为0）+1 = 1。因此第四个元素的Next值为上述的新构建的首串尾元素的索引值 （第三个元素的Next值） + 1即2。
第五步：讨论第四个元素的Next值，从而决定第五个元素的Next值。（基本上与第四步相同）发现第五个元素无法匹配时，第四个元素（b）与其Next值（2）对应的元素（b）（第二个元素）相同，因此第四个元素必定在一个具有相同首尾的串的尾串中，并且扮演最尾元素的角色，其串长为（（首元素的Next值为0，在这里阻止递归，约定其串长为0）+1 ） + 1= 2。因此第五个元素的Next值为上述的新构建的首串尾元素的索引值 （第四个元素的Next值） + 1即3。
第六步：讨论第五个元素的Next值，从而决定第六个元素的Next值。发现第六个元素无法匹配时，第五个元素（d）与其Next值（3）对应的元素（a）（第三个元素）不相同，也不与第三个元素的Next值（1）对应的元素（a）相同，如此递归都无法找到一个相同的元素构成相同首尾的串。因此第一直到第五个元素构成的串不存在相同的首部和尾部，因此不存在免匹配的部分，因此第六个元素的Next值为首元素的索引值即为1。
第七步：讨论第六个元素的Next值，从而决定第七个元素的Next值。发现第七个元素无法匹配时，第六个元素（a）与其Next值（1）对应的元素（a）（第一个元素）相同，因此第六个元素必定在一个具有相同首尾的串的尾串中，并且扮演最尾元素的角色，其串长为（首元素的Next值为0，在这里阻止递归，约定其串长为0）+1 = 1。因此第七个元素的Next值为上述的新构建的首串尾元素的索引值 （第六个元素的Next值） + 1即2。
第八步：讨论第七个元素的Next值，从而决定第八个元素的Next值。发现第八个元素无法匹配时，第七个元素（b）与其Next值（2）对应的元素（b）（第二个元素）相同，因此第七个元素必定在一个具有相同首尾的串的尾串中，并且扮演最尾元素的角色，其串长为（（首元素的Next值为0，在这里阻止递归，约定其串长为0）+1）+1 = 2。因此第八个元素的Next值为上述的新构建的首串尾元素的索引值 （第七个元素的Next值） + 1即3。
第九步：讨论第八个元素的Next值，从而决定第九个元素的Next值。发现第九个元素无法匹配时，第八个元素（a）与其Next值（3）对应的元素（a）（第三个元素）相同，因此第八个元素必定在一个具有相同首尾的串的尾串中，并且扮演最尾元素的角色，其串长为（（（首元素的Next值为0，在这里阻止递归，约定其串长为0）+1）+1）+ 1= 3。因此第九个元素的Next值为上述的新构建的首串尾元素的索引值 （第八个元素的Next值） + 1即4。
第十步：讨论第九个元素的Next值，从而决定第十个元素的Next值。发现第十个元素无法匹配时，第九个元素（b）与其Next值（4）对应的元素（b）（第四个元素）相同，因此第九个元素必定在一个具有相同首尾的串的尾串中，并且扮演最尾元素的角色，其串长为（（（（首元素的Next值为0，在这里阻止递归，约定其串长为0）+1）+1）+ 1）+ 1= 4。因此第十个元素的Next值为上述的新构建的首串尾元素的索引值 （第九个元素的Next值） + 1即5。
第十一步：讨论第十个元素的Next值，从而决定第十一个元素的Next值。发现第十一个元素无法匹配时，第十个元素（a）与其Next值（5）对应的元素（d）（第五个元素）不相同。而和第五个元素d的Next值（3）对应的元素a相同，因此第十个元素必定在一个具有相同首尾的串的尾串中，并且扮演最尾元素的角色，其串长为（（（首元素的Next值为0，在这里阻止递归，约定其串长为0）+1）+1）+ 1= 3。因此第十个元素的Next值为上述的新构建的首串尾元素的索引值 （第五个元素的Next值） + 1即4。
实现
KMP
// T 模式串， S目标串， pos第几个字符之后搜索
// 约定索引起始值为1
void Index_KMP(SString S, SString T, int pos){
// i 目标串指针，j 模式串指针
i = pos; j = 1;
// 只要指针没有溢出对应的串
while( i <= length(S) && j <= length(T)){
// 如果将要和 目标串元素 匹配的元素是模式串首元素前一位的元素
// 或者
// 当前目标串元素 和 模式串元素可以匹配
// if (j == first_indexof(T) - 1 || S[i] == T[j]){
if(j == 0 || S[i] == T[j]){
// 指针各自右移一位
++i;
++j;
}else{
// 发生了失配，查Next数组移动模式串指针
j = next[j];
}
}
if (j > length(T)){
// 如果模式串指针溢出了（模式串指针匹配完毕了所有模式串中的元素）
return i - length(T);
}
else return 0;
}
Next
// T 模式串， next Next数组
// 约定索引起始值为1
void get_next(SString T, int &next[]){
// i 计算每一个元素Next值的指针，它只可能右移用于计算下一个元素的Next值
// j 用于指向 无法找到头尾串时 的递归回溯的元素
// 初始化第一个元素的Next值
i = 1; next[1] = 0; j = 0;
while(i < length(T)){
// 如果递归回溯到第一个元素，它的next值为0，就无法继续回溯 -> 下一位元素的 Next值 就会等于 第一个元素的索引（1 即 0 + 1）
// 如果 当前元素 等于 当前元素Next值对应的元素 -> 下一个元素的 Next值 就会等于 当前元素的Next值 + 1
if (j == 0 || T[i] == T[j]){
++i; ++j; next[i] = j;
}
else{
// 否则递归回溯j，将其指向更小的一个同首尾的子串的尾部 + 1
j = next[j];
}
}
}
Nextval
(以下的讨论假设不需要递归以简化讨论过程)
优化Next，当第i+1位失配的时候。通常，我们按照算法会比较 T[i] 和 T[next[i]]，若它们相同则将Next[i+1]设置成Next[i] + 1。但是，如果 T[Next[i] + 1]和失配元素（T[i+1]）相同时，这样设置则是多余的（Next元素的含义就是，某个元素失配时用哪个元素补充匹配，若补充匹配的元素和失配元素相同则这样设置是多余的）。所以，此时应该把Next[i+1]设置成Next[Next[i] + 1]，就是当Next[i]+1失配时应该用哪个元素补充匹配。
那为什么T[Next[Next[i] + 1]]不会等于T[i+1]呢？因为按照这样的算法递推是从第一个元素开始计算，可以确保除了当前失配的元素以外，之前的任意一个元素（索引为m）都不可能等于T[Next[m]+1]。
// T 模式串， next Next数组
// 约定索引起始值为1
void get_nextval(SString T, int &nextval[]){
// i 计算每一个元素Next值的指针，它只可能右移用于计算下一个元素的Next值
// j 用于指向 无法找到头尾串时 的递归回溯的元素
// 初始化第一个元素的Next值
i = 1; nextval[1] = 0; j = 0;
while(i < length(T)){
// 如果递归回溯到第一个元素，它的next值为0，就无法继续回溯
// 如果 当前元素 等于 当前元素Next值对应的元素
if (j == 0 || T[i] == T[j]){
++i; ++j;
if(T[i] != T[j]){
// 如果替补匹配的值不等于当前失配值,则设置它的索引为Next值
nextval[i] = j;
}
else{
// 否则设置它的Next值为当前失配值的Next值
nextval[i] = next[j];
}
}
else{
// 否则递归回溯j，将其指向更小的一个同首尾的子串的尾部 + 1
j = nextval[j];
}
}
}
后记
如果还是不能看懂Next数组的程序实现，推荐自己手动制作一下下图Next数组算法的逐帧动画，会帮助理解很多。