KMP

“KMP”是由三位科学家的名字首字母组成的——Knuth-Morris-Pratt。这个算法用来解决字符串匹配问题：在一个文本串中查找一个模式串有没有出现，以及出现的位置。

为什么需要kmp

最朴素的字符串匹配：拿模式串从主串的每一个位置开始逐个字符比较，一旦发现不匹配，就把模式串往后挪到主串的下一位，重新从头开始比较。

每次失配后，模式串指针都会回退，最坏的情况是时间复杂度是O(nm)（n是主串长度，m是模式串长度）。

思想

当字符串发生失配的时候，我们已经知道之前匹配成功的那部分字符是什么，这部分信息不会被浪费。利用这些已知信息，可以避免主串指针的回退。

我们先预处理模式串，构造一个ne[]数组：统计最长相等前后缀的长度。

ne[j]就表示模式串前j个字符构成的字串中，最长相等前后缀的长度。

举个例子，模式串p = ababc（下标从1开始），预处理出来的ne数组是[0, 0, 1, 2, 0]。以ne[4] = 2为例：p前四个字符是“abab”，它最长的相等前后缀是“ab”（前缀“ab”和后缀“ab”），长度为2。

为什么失配时可以直接跳到ne[j]，而不用把指针退回起点？

假设主串s在匹配到"ababa..."时，前4个字符"abab"和模式串p完全匹配（此时j=4），但第5个字符失配了（s[5]='a'，而p[5]='c'）。这时候不需要把j退回0重新开始比较，因为已经匹配上的这一段"abab"，本身就等于模式串p的前4个字符。p的前4个字符里，前缀"ab"和后缀"ab"是相等的。也就是说，s中刚刚失配位置往前数2个字符，其实已经天然地和模式串p的前2个字符对齐了。所以可以直接让j = ne[4] = 2，从p的第3个字符（j+1位置）继续和s的当前字符比较，不用退回起点重新扫。

复杂度

KMP总体是O(n + m)

1. 构造ne数组是O(n)

vector<int> getNext(const string& p) {
    int n = p.size();
    vector<int> nxt(n, 0);
    for (int i = 1, k = 0; i < n; i++) {
        while (k && p[i] != p[k]) k = nxt[k - 1];
        if (p[i] == p[k]) k++;
        nxt[i] = k;
    }
    return nxt;
}

不是O(n²)，这里用均摊分析。

2. 主匹配过程是O(m)

void solve() {
    int n, m;
    string p, s;
    cin >> n >> p >> m >> s;

    auto nxt = getNext(p);
    vector<int> res;

    for (int i = 0, k = 0; i < m; i++) {
        while (k && s[i] != p[k]) k = nxt[k - 1];
        if (s[i] == p[k]) k++;
        if (k == n) {
            res.push_back(i - n + 1);
            k = nxt[k - 1];
        }
    }

    for (int i = 0; i < (int)res.size(); i++)
        cout << res[i] << " \n"[i + 1 == (int)res.size()];
}

均摊分析。

谢谢。