KMP算法详解

呼——终于看懂了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;
}