KMP 算法 - 字符串匹配

算法原理

KMP 算法用于在一个字符串（文本）中查找另一个字符串（模式）的所有出现位置。

核心思想

预处理：计算模式串的 Next 数组（部分匹配表）
匹配优化：利用 Next 数组，避免不必要的回溯
时间复杂度：预处理 $$ O(m) $$，匹配 $$ O(n) $$，总计 $$ O(n + m) $$

Next 数组含义

Next[i] 表示模式串前 i 个字符的最长相等前后缀长度：

前缀：不以最后一个字符结尾的子串
后缀：不以第一个字符开头的子串

文本串：模式串：

速度：

点击"初始化"开始

Next 数组

文本串（主串）

模式串

匹配日志


void buildNext(const string& p, vector& next) {
    int n = p.length();
    next.assign(n, 0);
    next[0] = -1;
    int j = -1;

    for (int i = 1; i < n; i++) {
        while (j >= 0 && p[i] != p[j + 1])
            j = next[j];  // 回溯
        if (p[i] == p[j + 1])
            j++;
        next[i] = j;
    }
}

vector KMP(const string& s, const string& p) {
    int n = s.length(), m = p.length();
    vector next(m), result;

    buildNext(p, next);

    int j = -1;
    for (int i = 0; i < n; i++) {
        while (j >= 0 && s[i] != p[j + 1])
            j = next[j];  // 利用 Next 数组跳过
        if (s[i] == p[j + 1])
            j++;
        if (j == m - 1) {
            result.push_back(i - m + 1);  // 匹配成功
            j = next[j];
        }
    }

    return result;
}

为什么 KMP 更快？

暴力匹配在失配时，模式串每次只能右移一位。KMP 利用已匹配的信息，直接跳过不可能匹配的位置。

例子：文本串 ABABDABACDABABCABAB，模式串 ABABCABAB