KMP算法
KMP算法(Knuth–Morris–Pratt algorithm)是一种快速模式串匹配算法，其核心是next数组的求解和使用。时间复杂度 $O(mn)$，与BF等需要回溯的算法相比， KMP算法具有极高的性能。
next数组的求解
next数组的含义是：next[i]为i之前的字符串的前缀和后缀的共有元素的最长长度。具体计算可以有递推式产生。若pattern[i] == pattern[j],则pattern[i+1] = pattern[j+1],否则，依次使j = next[j],向前寻找匹配位置。具体实现代码如下：
void getNext(int next[], char pattern[])
{
int i = 0, j = -1;
while (pattern[i] != '\0') {
if (j == -1 || pattern[i] == pattern[j]) {
next[++i] = ++j;
} else {
j = next[j];
}
}
}
还可以做一个小优化，提高匹配效率：
void getNext(int next[], char pattern[])
{
int i = 0, j = -1;
while (pattern[i] != '\0') {
if (j == -1 || pattern[i] == pattern[j]) {
++i;
++j;
// 再次判断i位置和j位置的字符的相等关系
if (pattern[i] == pattern[j]) {
next[i] = next[j];
} else {
next[i] = j;
}
} else {
j = next[j];
}
}
}
匹配
在匹配过程中，就可以充分利用next数组，在很次失配时尽可能向前移动，提高匹配段的效率，具体实现如下：
/* return the first position of pattern appears in src string.
* if the pattern doesn't appear, return -1.
**/
int kmp(char src[], char pattern[], int next[])
{
int i = 0, j = 0;
while (str[i] != '\0' && pattern[j] != '\0') {
/**
* j == -1: 源字符串中当前字符失配。
* src[i] == pattern[j]: 当前位置匹配，两个指针都要后移。
**/
if (j == -1 || src[i] == pattern[j]) {
++i;
++j;
} else {
j = next[j]; // when match failed, jump to next[j].
}
}
if (pattern[j] == '\0') { // get to the end of pattern string.
return i - strlen(pattern);
} else {
return -1; // failed.
}
}
KMP算法寻找pattern在src中出现的次数
寻找模式串出现次数，只需要在原来的寻找出现位置的基础上稍作修改即可，具体实现如下：
/* return the times of pattern appears in src string.
**/
int kmp(char src[], char pattern[], int next[])
{
int i = 0, j = 0, ans = 0;
while (str[i] != '\0') {
if (j == -1 || src[i] == pattern[j]) {
++i;
++j;
} else {
j = next[j]; // when match failed, jump to next[j].
}
if (pattern[j] == '\0') { // get to the end of pattern string.
ans++;
j = next[j];
i--;
}
}
return ans;
}
另一种实现方法：
/* return the times of pattern appears in src string.
**/
int kmp(char src[], char pattern[], int next[])
{
int i = 0, j = 0, ans = 0;
for (i = 0; src[i] != '\0'; ++i) {
while (j > 0 && src[i] != pattern[j]) {
j = next[j];
}
if (src[j] == pattern[i]) {
j++;
}
if (pattern[j] == '\0') { // get to the end of pattern.
ans++;
j = next[j];
}
}
return ans;
}
关于字符串匹配
某种意义上讲，AC自动机算法相当于是Trie上进行的KMP，其失败指针的含义类似于KMP算法中的next数组。
此外，若只需要判断多个模式串在源字符串中是否存在，则Trie图算法相当于路径压缩的AC自动机。或者说，AC自动机和Trie图分别为字符串匹配的有限状态自动机DFA的 不同表达形式。
扩展KMP
扩展KMP问题定义：
| 给定字母串 S，T，定义 n = | S | , m = | T | , extend[i]=S[i..n] 与 T 的最长公共前缀长度。 |
要求在线性时间内求出所有的 extend[1..n] 。
分析
扩展KMP算法的核心在于如何利用已经求出的前缀长度来减少比较次数。用 next[i] 来表示 T[i..m] 与 T 的最长公共前缀长度。不难建立起 next 数组与 extend 数 组之间的关系。不难发现：计算 next 数组的过程实际上也是一个以 T 为母串、T 为字串的扩展 KMP 算法过程。
实现
[刘雅琼的PPT][1]中给出了一个扩展KMP的实现。代码如下所示（有改动）：
/**
* Extend KMP algorithm.
* This implemention is modified from the code in Liu YaQiong's slides.
*/
void extendKmpLYQ(char pattern[], char str[], int next[], int extend[]) {
int a(0), p(0), pLen(strlen(pattern)), sLen(strlen(str));
for(int i = 0, j = -1; i < sLen; ++i, --j) {
if(j < 0 || i + next[i-a] >= p) {
if(j < 0) {
j = 0, p = i;
}
while(p < sLen && j < pLen && str[p] == pattern[j]) {
++p, ++j;
}
extend[i] = j, a = i;
}
else {
extend[i] = next[i-a];
}
}
}
运行该算法时，只需要先将 T 即作为母串又作为字串求出 next 数组，在求 extend 数组的值。
int next[1000] = {0}, extend[1000] = {0};
char S[1000] = {'\0'}, T[1000] = {'\0'};
extendKmpLYQ(T, T, next, next);
extendKmpLYQ(T, S, next, extend);