呼——终于看懂了KMP——磕了三天了。
Q: KMP是干什么的？
- 是查找字符串用的，可以查找到 \(S2\) 字符串在 \(S1\) 字符串中出现的位置（当然，你可以统计出次数）。
Q: 那复杂度是多少的？
- 通常，我们认为他的复杂度是 \(O(|S1|)\)， 虽然有点常数。
常规的的比较方法是直接比较，枚举一个头，然后逐个比较，复杂度（喜提）\(O(|S1|\times|S2|)\)。慢就在于每次都要从头扫。很浪费时间 （浪费生命），那实在是太浪费了，有没有快点的办法呢？如果一个串，的开头已经确定了和我是一样的，那不就可以少用时间了吗？
我们希望（它/他/她）跳的尽可能远，但是不能漏掉，这样就可以节约大把的时间 （生命）。哪么可以找到 \(S2\) 对于每个 \(i( 1 \le i \le n)\) \(next_i\) 表示 \(S2[0, i - 1]\) 中最大 / 前缀和后缀相同 / 的长度，那么我们就可以在前缀匹配失败后跳转到后缀匹配。 \(next\) 数组之和 \(S2\) 相关， 所以可以预处理。
现在问题就变成了如何预处理上了。
假设红色[0 ~ j]的和橙色的 [i-j-1 ~ i-1] 已经匹配出来了，相等。那么接下来要匹配 \(j + 1\) 和 \(i + 1\)。假设最好情况 $ S2[j + 1] == S2[i]$, j++就好了。但是如果不等于呢？
那么我们就要比较[0, j - 1] 和 [i - j] 了， 但是又变回了 \(O(n ^ 2)\)。其实我们可以转换一下，反正橙色[i-j-1 ~ i-1]的和红色[0 ~ j]的一致，我们不妨把橙色的后缀移到前面来。
那么，这时我们就会发现我们要找的 \(j\) 应该变换的值我们之前求过是 \(next[j]\)， 直接调用，但是为了避免没法匹配 while 就好了。
上代码吧，有注释的啦
#include <iostream>
using namespace std;
const int kMaxN = 1e6 + 5;
string s1, s2;
int l1, l2, net[kMaxN]; //最大前缀和后缀相同的长度， 因为next是关键词，所以用net替代
int main() {
cin >> s1 >> s2;
l1 = s1.size(), s1 = " " + s1; //舒服一点
l2 = s2.size(), s2 = " " + s2;
int j = 0; //此时最长（既匹配到哪一位）
for (int i = 2; i <= l2; i++) { //预处理
while (j && s2[i] != s2[j + 1]) { //j已经为0就不用跳了
j = net[j]; //不行就往回跳
}
if (s2[i] == s2[j + 1]) {//如果比较成功，j++
j++;
}
net[i] = j;//赋值上
}
j = 0;
for (int i = 1; i <= l1; i++) {
while (j && s1[i] != s2[j + 1]) {
j = net[j]; //匹配失败就往回跳
}
if (s1[i] == s2[j + 1]) { //如果比较成功，j++
j++;
}
if (j == l2) { //成功就输出
cout << i - l2 + 1 << '\n';
j = net[j];
}
}
for (int i = 1; i <= l2; i++) { //题目最后的要求
cout << net[i] << ' ';
}
return 0;
}