KMP 算法CSP-S

💡 核心思想

KMP（Knuth-Morris-Pratt）算法用于在文本串中查找模式串的所有出现位置。核心是预处理 next 数组（前缀函数），表示模式串中每个位置的最长相等真前后缀长度。匹配失败时利用 next 数组跳过已匹配的部分，避免回溯。

🎯 直觉理解

想象你在书里找一个长句子。朴素方法是逐个位置对齐比对，失败了从头开始。KMP 的聪明之处是：如果你已经匹配了 "abcabc" 然后失败了，你不需要从头开始——因为你知道后面三个字符是 "abc"，它正好也是模式串的开头！所以可以直接跳到匹配 "abc" 的状态继续。

📝 算法流程

1. 求 next 数组：j = next[j-1] 回退找匹配
2. 匹配过程：失配时 j = next[j-1] 跳转
3. next[i] = s[0..i] 的最长公共前后缀长度
4. 时间复杂度 $O(n+m)$

$$next[i] = \max\{k : s[0..k-1] = s[i-k+1..i]\}$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
int main() {
    string text, pat; cin >> text >> pat;
    int n = text.size(), m = pat.size();
    // 求 next 数组
    vector<int> nxt(m, 0);
    for (int i = 1; i < m; i++) {
        int j = nxt[i-1];
        while (j > 0 && pat[i] != pat[j]) j = nxt[j-1];
        if (pat[i] == pat[j]) j++;
        nxt[i] = j;
    }
    // 匹配
    vector<int> ans;
    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && text[i] != pat[j]) j = nxt[j-1];
        if (text[i] == pat[j]) j++;
        if (j == m) { ans.push_back(i - m + 2); j = nxt[j-1]; }
    }
    for (int x : ans) cout << x << "\n";
    for (int x : nxt) cout << x << " ";
    return 0;
}

⚠️ 常见坑点

📚 相关题目