1 知识点

KMP算法已经集成到string类型的find()方法了，

但这里我们不用这个，我们自己来实现这个方法。

KMP算法的关键步骤：

1. p[N]表示输入模式串，求取该模式串的ne[]数组。ne[i]表示前缀等于后缀的长度，且它最长。也即p[1,j] = p[i-j+1,i]。
2. 循环目标串s[M]，利用ne[]数据，得到完全匹配模式串的下标位置，并输出。

//步骤（1）
for (int i = 2, j = 0; i <= n; i ++ )
{while (j && p[i] != p[j + 1]) j = ne[j]; //i表示后缀末尾，j + 1表示前缀末尾。if (p[i] == p[j + 1]) j ++;ne[i] = j;
}
//步骤（2）
for (int i = 1, j = 0; i <= m; i ++ )
{while (j && s[i] != p[j + 1]) j = ne[j]; //发生了冲突之后，看它前一位的next数组值，即ne[j]，而不是ne[j + 1]//i表示文本串"aabaabaaf"的下标，j表示模式串"aabaaf"的下标。if (s[i] == p[j + 1]) j ++ ;if (j == n){printf("%d ", i - n);j = ne[j];}
}

最长相等前后缀，

以字符串aabaabaaf、模式串aabaaf为例，讲解KMP算法。

首先计算模式串aabaaf的next数组，即最长相等前后缀。计算如下，

a 无前缀与后缀 最长相等前后缀为0
aa 最长相等前后缀为1
aab 最长相等前后缀为0
aaba 最长相等前后缀为1
aabaa 最长相等前后缀为2
aabaaf 最长相等前后缀为0

故next数组如下，

next[1] = 0, next[2] = 1, next[3] = 0, next[4] = 1, next[5] = 2, next[6] = 0.

实现代码如下，

const int N = 1e6 + 10;
char p[N];
int ne[N];
cin >> p + 1; //输入模式串"aabaaf"
for (int i = 2, j = 0; i <= n; i ++ )
{while (j && p[i] != p[j + 1]) j = ne[j];if (p[i] == p[j + 1]) j ++;ne[i] = j;
} 

计算next数据的主要步骤有，

1. 初始化
2. 处理前后缀末尾字符不相同的情况，i表示后缀末尾，j + 1表示前缀末尾。
3. 处理前后缀末尾字符相同的情况，
4. 后缀末尾+1

2 模板

输入示例为，

3
aba
5
ababa

输出示例为，

0 2

代码为，

#include <iostream>using namespace std;const int N = 1e6 + 10;
int n, m;
char p[N], s[N];
int ne[N];int main() {cin >> n >> p + 1 >> m >> s + 1;//求取next数组for (int i = 2, j = 0; i <= n; ++i) {while (j && p[i] != p[j + 1]) j = ne[j];if (p[i] == p[j + 1]) j++;ne[i] = j;}//返回匹配的下标位置for (int i = 1, j = 0; i <= m; ++i) {while (j && s[i] != p[j + 1]) j = ne[j];if (s[i] == p[j + 1]) j++;if (j == n) {cout << i - n << " ";j = ne[j];}}cout << endl;return 0;
}

使用C++库函数实现的版本如下，

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int main() {int n, m;string p, s;cin >> n >> p >> m >> s;int pos = s.find(p);while (pos != string::npos) {cout << pos << " ";pos = s.find(p, pos + 1);}cout << endl;return 0;
}