图解 KMP 算法
KMP是三位大牛：D.E.Knuth、J.H.Morris 和 V.R.Pratt 同时发现的。其中第一位就是《计算机程序设计艺术》的作者！！
快速模式匹配算法，简称 KMP 算法，是在 BF 算法基础上改进得到的算法。
- BF 算法一个一个挨个匹配，它没有从上一次匹配中学会任何东西。事实上，一次匹配失败能够告诉我们，匹配失败之前的字符都是匹配成功的。利用这一点，我们很容易推导出 KMP 算法的基本思想。
前缀后缀的最大公共长度
-
「前缀（prefix）」指的从原字符串的尾部删除 0 个或多个字符得到的串，例如模式串 "ABCD"，则 "A"、"AB"、"ABC" 以及 "ABCD" 都属于前缀字符串
-
「后缀（suffix）」指的从原字符串的开始处删除0个或多个符号后得到的串，还拿模式串 "ABCD" 来说，"D"、"CD"、"BCD" 和 "ABCD" 为后缀字符串。
-
「真前缀（前缀真子串）」是指不包含自身的前缀。
-
「真后缀（后缀真子串）」是指不包含自身的后缀。
-
注意：后面提到的前缀后缀，统一指真前缀和真后缀！
-
前缀后缀的最大公共长度如：
| 字符串 | 前后缀最大公共长度 |
|---|---|
| ABA | 1 |
| ABAB | 2 |
| ABCABC | 3 |
一般的，若 str 字符串的前后缀的最大公共长度为 l，可以画如下示意图，黄色表示公共段部分。
KMP 算法的基本思想
跳过不可能成功的字符串比较
每次失配后，KMP 算法并没有像 BF 算法往下挨个再匹配，KMP 算法每一次失配后，下次匹配移动的步长由模式串中失配的位置决定，由此来保证不做不可能的比较。
那么那些情况下一定是不可能的比较？
到底移动多少步能跳过这些不可能的比较呢？
如图，模式串与主串某处失配后，先求出模式串匹配部分 A 的前缀后缀最大公共长度：
下面列出了一些不可能的情况：
事实上，在当前缀最大公共部分在后缀最大公共部分之前的匹配都是不可能的：
这里使用反证法可以证明，假设上图的匹配是可能的，可得出字符串 A 有更大的前缀后缀最大公共长度，与刚刚求得的 A 的前缀后缀最大公共长度矛盾，因此匹配是不可能的。上述命题得证。
最后取逆否命题，可得：前缀最大公共部分前后位置不超过后缀最大公共部分是匹配可能的必要条件，因此直接跳过不可能的比较，从下图中可能的比较位置开始进行第二次匹配。
综上，可以总结出 KMP 算法的基本思路：
一次失配后，由失配位置确定匹配部分的前缀后缀最大公共长度，由最大公共长度确定下一次匹配的移动步长，然后进行下一次匹配，以此类推。
还可以总结出：
每次匹配失败后，模式串移动的步长仅与模式串本身有关，与主串无关。
相对于模式串，当失配位置相同，下次匹配移动步长相同，因为前面匹配段相同，前缀后缀最大公共长度也相同。
当失配位置不同时，下次匹配移动步长可能不同。
因此，匹配前先将模式串每个位置的之前的字符串的前缀后缀最大公共长度求出来，就可以确定任何情况下失配后，需要移动多少步长才能进行下一次匹配，这就是下面要讲到的
next数组求解：
next 数组的求解
如下图，显示了一次匹配失败后，下一次匹配开始，模式串的移动：
实际代码中，使用指针的重定位来实现模式串的移动：
-
因此，可以给每个模式串配备一个数组（例如 next[]），用于存储模式串中每个字符对应指针 j 重定向的位置
-
模式串中各字符对应 next 值的计算方式是，取该字符前面的字符串（不包含自己），其前缀后缀最大公共长度就是该字符对应的 next 值。
注意：
- 模式串第一个位置对应的 next 值应该为 -1，它的含义是：
- 第一个字符开始就失配，此时
j = 0不需要重定位， -1 表示主串的指针i = i + 1，即从主串的下一个字符从头开始第二次匹配。
- 第一个字符开始就失配，此时
求 next[] 数组的思路类似于数学归纳法：
先求
next[1]，然后找到已知
next[i-1]求next[i]的一般方法这样，
next[]的所有值都能求出来了。
- 对于
next[1]，str[1]前面只有一个字符，一个字符的没有前缀和后缀，因此next[1] = 0
已知 next[i-1] 求 next[i]
令 j = next[i-1] ，确定 next[i] 的一种情况是：
如果，str[j] != str[i-1] 怎么确定 next[i] 呢？
考虑到 A 串 和 B 串 完全一致，求出 A 串 的前缀后缀最大公共长度（= next[j]），它等于 A 串 的前缀与 B串 的后缀的最大公共长度，因此只要做类似的比较（比较公共部分后一个字符是否相等），实际操作步骤如下：
① 令 j = next[j]; ;
② 然后比较 str[j] 和 str[i-1]，不相等，返回第①步继续迭代。如果相等，转③
③ next[i] = j + 1，i++ ，如果 i > strlen(str) 结束，返回 next[] 数组。否则转④
④ j = next[i-1] 转②
有些同学可能会怀疑上述方法的正确性，以上面所述过程为例：
第一步
j = 6而str[j] != str[i-1]，于是到第二步第二步
j = 2如果str[j] == str[i-1]，于是next[i]=2+1=3那么
next[i]有没有可能取 3~5 范围内的其他值呢，如何保证求出来的就是最大的公共长度？这个方法与前面证明不可能比较的方法类似，使用反证法，假设实际的公共长度大于 3，那么可得出
A 串 或 B 串的前缀后缀最大公共长度比求得的更大，矛盾，所以假设错误，该方法完全能够保证求出来的就是最大的公共长度。
求模式串 next [] 数组的算法实现：
/// 求模式串的 next[] 数组
/// @param str 模式串
/// @param next 返回的 next[] 数组
void Next(char* str, int next[]);
void Next(char* str, int next[])
{
next[0] = -1;
next[1] = 0;
int j;
for (int i = 1; i < strlen(str); i++)
{
j = next[i - 1];
while (j != -1 && str[j] != str[i - 1])
{
j = next[j];
}
next[i] = j + 1;
}
}
KMP 算法实现：
/// 串的模式匹配 KMP 算法
/// @param B 伪主串
/// @param A 伪子串
/// @param return 返回子串的在主串中的位置，如果 A 不是 B 的子串，则返回 -1
int KMP(char* B, char* A);
int KMP(char* B, char* A)
{
int* next = malloc(strlen(A) * sizeof(int));
Next(A, next);
int i = 0, j = 0;
while (i < strlen(B) && j < strlen(A))
{
if (B[i] == A[j])
{
i++;
j++;
}
else
{
if (next[j] == -1)
{
i++;
// 仅 i = 0,j = 0 情况下 next[j] 才可能等于 -1
// 所以 j = 0 可以不必写，严谨起见，写上
j = 0;
}
else
{
j = next[j];
}
}
}
free(next);
if (j == strlen(A))
{
i = i - strlen(A);
return i;
}
else
{
return -1;
}
}
Next 函数的缺陷
Next 函数无法避免另外一种不可能匹配的情况：
如果出现上图所示类似的情况，该怎么办？懒得打字了，用下图说明：
修正的 Next 函数
/// 求模式串的 next[] 数组
/// @param str 模式串
/// @param next 返回的 next[] 数组
void Next(char* str, int next[]);
void Next(char* str, int next[])
{
next[0] = -1;
next[1] = 0;
int j = 1;
for (int i = 2; i < strlen(str); i++)
{
j = next[i - 1];
while (j != -1 && str[j] != str[i - 1])
{
j = next[j];
}
j = j + 1;
while (j != -1 && str[j] == str[i])
{
j = next[j];
}
next[i] = j;
}
}
Next 函数修正前后比较
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/// 求模式串的 next[] 数组
/// @param str 模式串
/// @param next 返回的 next[] 数组
void Next(char* str, int next[]);
/// 求模式串的 next[] 数组
/// @param str 模式串
/// @param next 返回的 next[] 数组
void NextNew(char* str, int next[]);
/// KMP 算法
/// @param B 伪主串
/// @param A 伪子串
/// @param nextFun 指向求 next 数组的函数的函数指针
/// @return 返回子串在主串中的位置，若 A 不是 B 的子串，则返回 -1
int KMP(char* B, char* A, void(*nextFun)(char*, int[] ));
int main()
{
char A[] = "ACCACCACC";
char B[] = "ACBBABCCCACBACCACCACCBBACCCBBAB";
int* next = (int*)malloc(strlen(A) * sizeof(int));
int* nextNew = (int*)malloc(strlen(A) * sizeof(int));
Next(A, next);
NextNew(A, nextNew);
printf("next 修正前后数组比较：\n");
for (int i = 0; i < strlen(A); i++)
{
printf("%c\t", A[i]);
}
printf("\n");
for (int i = 0; i < strlen(A); i++)
{
printf("%d\t", next[i]);
}
printf("\n");
for (int i = 0; i < strlen(A); i++)
{
printf("%d\t", nextNew[i]);
}
printf("\n");
printf("两种 next 数组的 KMP 方法结果：\n");
printf("修正前：%d\n", KMP(B, A, Next));
printf("修正后：%d\n", KMP(B, A, NextNew));
return 0;
}
void Next(char* str, int next[])
{
next[0] = -1;
next[1] = 0;
int j;
for (int i = 1; i < strlen(str); i++)
{
j = next[i - 1];
while (j != -1 && str[j] != str[i - 1])
{
j = next[j];
}
next[i] = j + 1;
}
}
void NextNew(char* str, int next[])
{
next[0] = -1;
next[1] = 0;
int j = 1;
for (int i = 2; i < strlen(str); i++)
{
j = next[i - 1];
while (j != -1 && str[j] != str[i - 1])
{
j = next[j];
}
j = j + 1;
while (j != -1 && str[j] == str[i])
{
j = next[j];
}
next[i] = j;
}
}
int KMP(char* B, char* A, void(*nextFun)(char*, int[]))
{
int* next = malloc(strlen(A) * sizeof(int));
nextFun(A, next);
int i = 0, j = 0;
while (i < strlen(B) && j < strlen(A))
{
if (B[i] == A[j])
{
i++;
j++;
}
else
{
if (next[j] == -1)
{
i++;
j = 0;
}
else
{
j = next[j];
}
}
}
free(next);
if (j == strlen(A))
{
i = i - strlen(A);
return i;
}
else
{
return -1;
}
}