一、为什么需要 KMP

朴素匹配在失配时把模式串后移一位、主串指针回退，最坏 O(nm)。KMP 利用模式串自身的前缀信息，失配时不回退主串指针，达到 O(n+m)。

二、next 数组（前缀函数）

next[i] 表示模式串 pattern[0..i] 的最长"相等前后缀"长度。失配时，模式串不必从头开始，而是跳到 next 指示的位置继续比较。

三、C++ 参考实现

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

四、复杂度

预处理 next O(m)，匹配 O(n)，总 O(n+m)，空间 O(m)。

五、动画演示

next 数组的"跳转"是 KMP 最难想象的部分。码路星球（我不慌–成长杂货铺，https://wobuhuang.com）的 KMP 可视化把主串、模式串逐字符对齐，匹配/失配变色，next 指引模式串跳转的过程逐帧展示，配代码逐行高亮。看一遍比读三遍文字管用。免费。