KMP算法是由三位计算机科学家D.E.Knuth、J.H.Morrs、VR.Pratt发表的一个模式匹配算法。和BM算法类似，KMP算法也在减少没有必要的字符匹配，不过KMP算法的侧重点是在已匹配的前缀
思路
首先，我们来看一个例子，主串abcdefgab，模式串abcdex。在第一轮比较的时候，KMP算法和BF算法一样都是从首字母开始匹配。
abcdefgab
abcdex
第一轮匹配成功，则开始第二轮比较第二个字符，以此类推。
如果模式串后续不存在与首字母b相匹配的字符，那么我们可以忽略后面四次比较，直接把模式串移动到第六个字母开始匹配，即②③④⑤都是可以忽略的。之所以保留第⑥步是应为我们知道T[0]≠T[5]，但是不能确定T[1]≠S[5]。
如果存在重复字符又会怎么样呢？我们再来看一个例子，主串为abcabcabc、模式串为abcabx。比较如下：
因为模式串中前五个字符abcab中，最前面两个字符ab和最后面两个字符ab是相等的，所以上述④⑤两个步骤也可以省略。
对比这两个例子，我们发现去掉这些不必要的比较之后，i值就不会再回溯，那么我们就需要考虑j的变化了。而且我们也可以发现j的变化，其实和模式串中有没有相等的前缀后缀来确定的，和主串并没有关系。此时引入一个重要的概念，next数组。
next数组
next数组是一个一维的整形数组，它是KMP算法的核心，只要得到这个数组，我们就能确定每次遍历模式串如何进行回溯。那么如何来推导这个数组呢？
因为next数组是针对模式串的，那么next的长度就是模式串的长度。next数组分为两种情况，一种是字符串的第一个位置保存的是字符串的长度而非内容，第二种是第一个位置就是字符串的内容。需要注意的是，next数组对应的是当前字符之前的子串中的前后缀的匹配情况。
非标准串
字符串内容从下表为1开始，即第一个位置保存的是字符串的长度。
我们可以得到如下定义：
需要注意的是next数组默认从1开始，我们来做一下next数组的推导：
abcdex
- 当
j == 1时，默认next[1] = 0； - 当
j == 2时，j由1到j-1只有一个字符a，next[2] = 1； - 当
j == 3时，j由1到j-1只有一个字符ab，且a与b不相等，next[3] = 1； - 同理可得，
next[j] = 011111
abcabx
- 当
j == 1时，默认next[1] = 0； - 当
j == 2时，j由1到j-1只有一个字符a，next[2] = 1； - 当
j == 3时，同上，next[3] = 1； - 当
j == 4时，同上，next[4] = 1； - 当
j == 5时，子串为abca，此时前缀a与后缀a相等，符合第二种条件，即P1 = P4，由P1 = Pj-k+1可以得出k = 2，即next[5] = 2； - 当
j == 6时，子串为abcab，此时前缀ab与后缀ab相等，符合第二种条件，即P1P2 = P4P5，由P1Pk-1 = Pj-k+1Pj-1可以得出k = 3，即next[6] = 3； - 即
next[j] = 011123
ababaaaba
- 当
j == 1时，默认next[1] = 0； - 当
j == 2时，j由1到j-1只有一个字符a，next[2] = 1； - 当
j == 3时，同上，next[3] = 1； - 当
j == 4时，同上，子串为aba，此时前缀a与后缀a相等，符合第二种条件，即P1 = P3，由P1 = Pj-k+1可以得出k = 2，即next[4] = 2； - 当
j == 5时，子串为abab，此时前缀ab与后缀ab相等，符合第二种条件，即P1P2 = P3P4，由P1Pk-1 = Pj-k+1Pj-1可以得出k = 3，即next[5] = 3； - 当
j == 6时，子串为ababa，此时前缀aba与后缀aba相等，符合第二种条件，即P1P2P3 = P3P4P5，可以得出k = 4，即next[6] = 4； - 当
j == 7时，子串为ababaa，此时前缀a与后缀a相等，符合第二种条件，即P1 = P6，可以得出k = 2，即next[7] = 2； - 当
j == 8时，子串为ababaaa，此时前缀a与后缀a相等，符合第二种条件，即P1 = P7，可以得出k = 2，即next[8] = 2； - 当
j == 9时，子串为ababaaab，此时前缀av与后缀av相等，符合第二种条件，即P1P2 = P7P8，可以得出k = 3，即next[8] = 3； - 即
next[j] = 011234223
-
aaaaaaaab可以得出next[j] = 012345678
那么next数组如何用代码实现呢？如果我们遍历模式串找到每一个子串，然后再来对比子串对应的前后缀元素，来确定相等的个数，通过这样的方式来求next数组是比较麻烦的。通过指针回溯的方法相对来说要简单很多。下面我们来看看如果通过指针回溯的方式求出next数组：
- 由上面的公式可得，
next[1] = 0; - 使用指针
i来遍历模式串，使用指针j来进行回溯- 当
T[i] == T[j]，通过i++、j++，即可得到下一个字符对应的next数组值，即next[i] = j。 - 当
T[i] != T[j]，则需要将j回溯到合理的位置。注意，此处是一个重点。什么位置是合理的位置呢？比如说aabaaxaaa，当我们遍历到第七个a的位置，即子串是aabaax，此时b和x不相等(j=3,i=6)，没有可匹配的前后缀，我们就需要回溯，因为之前第一、二个a和第四、五个a已经匹配成功，就回溯到第二个a进行和x比较，即回溯到j=2的位置。aabaaxaaa的next数组为012123123，即可得出j = next[j] = 2。 - 当回溯也匹配不上时，最终会走到
j = next[1] = 0，即从头开始匹配，依据公式得出next[i] = 1。
- 当
代码实现如下：
//注意字符串T[0]中是存储的字符串长度; 真正的字符内容从T[1]开始;
void getNexts(String T,int *next){
int i = 1;
int j = 0;
next[1] = 0;
while (i < T[0]) {
if (j == 0 || T[i] == T[j]) {
// i==0的时候说明回溯的时候没有匹配的 也就是不存在相等的前后缀
i += 1;
j += 1;
next[i] = j;
} else {
// 如果字符不相同,则j值回溯;
// 回溯到上一个比较位置 如果还不相同就继续回溯
// 一直回溯到j=1的时候值如果还是没有那就说明整个子串中没有相对应的前后缀元素 则直接将next的值置为1
j = next[j];
}
}
}
得出了next数组，那我们就可以使用它来做模式串匹配了。匹配的过程就和BF算法一样了，唯一不同的地方就是当字符出现不匹配的时候，主串不需要回溯，回溯的是模式串。
// T[0] 和 S[0] 存储的是字符串T与字符串S的长度
int KMP(String S, String T) {
if (S == NULL || T == NULL || T[0] == 0 || S[0] <= T[0]) {
return 0;
}
int i = 1;
int j = 1;
int *next = (int *)malloc(sizeof(int) * (T[0] + 1));
getNexts(T, next);
//若i小于S长度并且j小于T的长度是循环继续;
while (i <= S[0] && j <= T[0]) {
//如果两字母相等则继续,并且j++,i++继续比较
if(j == 0 || S[i] == T[j]) {
i += 1;
j += 1;
} else {
//如果不匹配时,j回溯到next中对应的位置
j = next[j];
}
}
if (j > T[0]) {
return i - T[0];
} else {
return -1;
}
}
从代码可以看出，KMP算法的时间复杂度为O(m+n)，相比于BF算法，还是有比较大的提高的。但是上述实现中还是有缺陷的，比如主串S= aaaabcde，模式串T= aaaaax，next数组是012345。匹配的过程如下：
其实，在i=5, j=5的时候可以得到b≠a，所以②③④⑤这几步的回溯是没有意义的。由于模式串的前几位字符都是相等的，所以我们可以用next[1]的值去替代后几位next[j]的值，从而达到优化的目的。
我们推导一下新数组nextval的实现：
- 模式串
aaaaax的next[j] = 012345
- 当
j == 1时，默认nextval[1] = 0； - 当
j == 2时，第2位字符为a，next[2] = 1，第1位的字符为a，相等，nextval[2] = nextval[1] = 0； - 当
j == 3时，因为第3位的字符为a，next[3] = 2，第2位的字符为a，相等，所以nextval[3] = nextval[2] = 0； - 当
j == 4时，因为第4位的字符为a，next[4] = 3，第3位的字符为a，相等，nextval[4] = nextval[3] = 0； - 当
j == 5时，因为第5位的字符为a，next[5] = 4，第4位的字符为a，相等，nextval[5] = nextval[4] = 0； - 当
j == 6时，因为第6位的字符为x，next[6] = 5，第5位的字符为a，不相等，nextval[6] = next[6] = 5； - 即
nextval[j] = 000005
- 模式串
abcabx的next[j] = 011123
- 当
j == 1时，默认nextval[1] = 0； - 当
j == 2时，第2位字符为b，next[2] = 1，第1位的字符为a，不相等，nextval[2] = next[2] = 1； - 当
j == 3时，因为第3位的字符为c，next[3] = 1，第1位的字符为a，不相等，所以nextval[3] = next[3] = 1； - 当
j == 4时，因为第4位的字符为a，next[4] = 1，第1位的字符为a，相等，nextval[4] = nextval[1] = 0； - 当
j == 5时，因为第5位的字符为b，next[5] = 2，第2位的字符为b，相等，nextval[5] = nextval[2] = 1； - 当
j == 6时，因为第6位的字符为x，next[6] = 3，第3位的字符为c，不相等，nextval[6] = next[6] = 3； - 即
nextval[j] = 011013
优化后代码如下：
void getNextvals(String T,int *nextval){
int i = 1;
int j = 0;
nextval[1] = 0;
while (i < T[0]) {
if (j == 0 || T[i] == T[j]) {
i += 1;
j += 1;
if (T[i] != T[j]) {
nextval[i] = j;
} else {
// 当前字符和前缀字符相同，则把前缀字符的nextval值赋给当前字符
nextval[i] = nextval[j];
}
} else {
j = nextval[j];
}
}
}
通过执行代码，我们可以看到示例kmp("abcddddabcabx", "abcabx")在优化前会循环14次，优化之后会循环13次，而示例kmp("aaaaabaabaaaaax", "aaaaax")在优化前会循环22次，优化之后会循环16次。
标准串
字符串第一个位置元素即为字符串的内容。可以得到如下定义：
这个推导过程和上面的一样，就不在此赘述了。比如issip得到next数组为-10001。
下面我们来看一下代码实现：
void getNexts(char *T, int *next, int tlen) {
int i = 0;
int j = -1;
// 默认next[0] = -1
next[0] = -1;
while (i < tlen - 1) {
if (j == -1 || T[j] == T[i]) {
j++;
i++;
next[i] = j;
} else {
j = next[j];
}
}
}
int kmp(char *S, char *T) {
int slen = (int)strlen(S);
int tlen = (int)strlen(T);
if (tlen == 0) {
return 0;
}
if (tlen > slen) {
return -1;
}
int *next = (int *)malloc(sizeof(int) * tlen);
getNexts(T, next, tlen);
int i = 0;
int j = 0;
while (i < slen && j < tlen) {
if (S[i] == T[j]) {
if (j == tlen - 1) {
return i - tlen + 1;
}
j += 1;
i += 1;
} else {
if (next[j] >= 0) {
j = next[j];
} else {
// 模式串起始位置不相等的话 主串需要移动一位 模式串需要回溯到第一个字符位置
j = 0;
i += 1;
}
}
}
return -1;
}
其优化和上面类似，就不赘述了。
总结
KMP算法的通过添加辅助数组next，减少了模式匹配中不必要的回溯。其空间复杂度为next数组的长度，即O(n)，其时间复杂度为生成next数组时的O(n)加上遍历主串时的O(m)，即O(m+n)。KMP算法的核心在于计算next数组，而计算next数组的关键则是模式串子串中最长可匹配的前后缀。
