前言
KMP算法是Knuth、Morris、Pratt三人在BF算法的基础上同时提出的模式匹配的高效算法。本文以字符串匹配问题为例，以通俗易懂的语言对KMP算法进行逻辑分析、数学证明和代码实现。本文需要读者对BF算法有一定了解。阅读本文，读者能够清楚理解KMP算法的核心思想和代码逻辑，并自主实现该算法。
优化策略
在BF算法中，每次子串匹配失败后，i指针(遍历主串)会回退到begin位置的下一个位置，j指针(遍历子串)会回退到子串的起始位置。假设主串的长度为M，子串的长度为N，同时回退i指针和j指针，时间复杂度为O(MN)。如果字符串中重复字符较多，该算法就显得非常低效。
BF算法：
int BfSolution::BF(string str, string sub)
{
int StBegin = 0;
int SuBegin = 0;
int i = 0;//遍历主串
int j = 0;//遍历子串
while (i < str.length() && j < sub.length())
{
if (str.at(i) == sub.at(j)) {
i++;
j++;
}
else {
StBegin++;
i = StBegin;
j = SuBegin;
}
}
if (j == sub.length()) {
return StBegin;
}
else {
return -1;
}
}KMP算法的优化策略为：匹配过程中i不回退，j回退到一个特定的位置，该位置不一定是起始位置，而需要做特定计算。
下面对j回退的“特定的位置”做一个说明。需要注意的是，我们的目的是将主串和子串进行匹配，这个过程中i不会回退，所以j回退的位置应该为主串和子串已经尽量匹配的位置。例如下面两个字符串，两字符串在i、j位置匹配失败，若按照BF算法思想，则应将i回退到StBegin位置，将j回退到起始位置，
但是通过观察发现，i位置前面的a、b已经和子串的前两个a、b有了很大程度的匹配，所以我们大可以将j回退到k的位置，i不回退，然后j从k位置继续向后判断和匹配。这里的k位置即是我们需要的“特定的位置”。也就是说，我们需要找到j位置之前的真子串与i位置之前的真子串有最大程度匹配的位置。寻找该位置的过程，就是next数组的计算过程。
next数组的计算
什么是next数组
上文说到，我们需要计算一个j匹配失败后回退的位置，这个位置(下标)其实就是next数组的一个元素。在实际匹配的过程中，每个位置都有可能匹配失败，所以我们需要针对子串的每个位置进行在该位置匹配失败后回退位置的计算，将计算的结果用一个一维数组维护，这个数组就是next数组。next数组记录了在各个位置匹配失败后j应回退到的位置。
手动计算next数组
我们先尝试手动计算next数组，在理解next数组的基本计算方法后，再探讨next数组计算中的规律，并用代码实现对next数组的计算。在下文中继续以k作为j回退的位置，即next数组的元素。
通过阅读上文你已经知道，计算next数组其实就是要找到i、j位置之前的子串最大程度匹配的位置(k)。在实际计算过程中，我们只考虑模式串（子串）的内容，所有的计算过程都是针对模式串（子串）的。
继续观察下面的字符串，i和j既然能够到达当前的位置，就说明i之前和j之前的字符串是完全匹配的，所以1部分和3部分一定相同，所以我们的问题就转化成了在A位置之后、B位置之前寻找两个相同的子串，这两个子串其中一个以0位置开头，另一个子串以j - 1位置结尾。不难发现，找到的两个子串的长度即为我们上文得到的位置。
由此我们得到计算k的方法：寻找两个分别以0位置开头，以j - 1位置结尾的两个相同子串，这两个子串的长度即为 k 。
一个练习
计算下面模式串的next数组
答案：
需要注意的是，计算过程中两个子串必须严格遵循“分别以0位置开头，以j - 1位置结尾”，两子串重合的情况也包含在内。规定next[0] == -1。
next数组计算中的规律
为了下面的说明和证明方便，规定模式串为p，从i位置回退到的位置依然为k。
如果我们知道next[i] = k，那如何计算next[i + 1]呢？
p[i] == p[k]时
通过上面的计算我们发现：当p[i] == p[k]时，有next[i + 1] == k + 1成立。例如上面练习中的字符串，当i == 4时，有k1==next[i] == 1，p[i] == 'b' ，p[k] == 'b'，且k2==next[i + 1] == 2。
下面给出这个规律的数学证明。
数学证明
证明：当p[i] == p[k]时，若next[i] == k，则有next[i + 1] == k + 1
前提：next[i] == k成立。为了下文表述方便，用p[x]~p[y]表示从x位置到y位置的字符串。
假设next[i] == k成立，则有p[0] ~ p[k - 1] == p[x] ~ p[i - 1]，因为有两子串的长度相等，则有k - 1 - 0 == i - 1 - x，得到x == i - k，即
void KmpSolution::getNext(int*& next, string sub)
{
next[0] = -1;
int k = -1;//k一直是前一项(sub.at(i - 1))的k
for (int i = 1; i < sub.length(); )
{
if (k == -1 || sub.at(i - 1) == sub.at(k)){
next[i] = k + 1;
k++;//这种情况k应该自增1
i++;
}
else {
k = next[k];
}
}
}
/*
@param str 主串
@param sub 模式串
@param i 遍历主串
@param j 遍历模式串
*/
int KmpSolution::KMP(string str, string sub)
{
int i = 0;
int j = 0;
int lenStr = str.length();
int lenSub = sub.length();
int* next = new int[lenSub];
getNext(next, sub);//计算next数组
while (i < lenStr && j < lenSub)
{
if (j == -1 || str.at(i) == sub.at(j)){
i++;
j++;
}
else {
j = next[j];
}
}
if (j == lenSub) {
return i - j;
}
else {
return -1;
}
}
