KMP 算法

概念讲解

什么是 KMP？

KMP 是一种字符串匹配算法，能在 $O(n+m)$ 时间内完成模式匹配。

核心思想

利用已匹配信息，避免重复匹配。

next 数组

定义

next[i] 表示模式串 P[0..i] 的最长相等前后缀长度。

构建

12345678910111213vector<int> buildNext(string pattern) {
    int m = pattern.size();
    vector<int> next(m, 0);
    int j = 0;
    for (int i = 1; i < m; i++) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j-1];
        }
        if (pattern[i] == pattern[j]) j++;
        next[i] = j;
    }
    return next;
}

KMP 匹配

12345678910111213141516vector<int> kmp(string text, string pattern) {
    vector<int> next = buildNext(pattern);
    vector<int> result;
    int j = 0;
    for (int i = 0; i < text.size(); i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = next[j-1];
        }
        if (text[i] == pattern[j]) j++;
        if (j == pattern.size()) {
            result.push_back(i - j + 1);
            j = next[j-1];
        }
    }
    return result;
}

时间复杂度

• 构建 next：$O(m)$
• 匹配：$O(n)$
• 总计：$O(n + m)$

考点分析

初赛考查方式

1. 程序阅读： KMP 程序
2. 编程题： 字符串匹配

常见考点

• next 数组
• KMP 匹配过程
• 循环节

例题精讲

例题 1：next 数组

题目： 求 "ABABC" 的 next 数组。

解答：

next = {0, 0, 1, 2, 0}

练习题

1. next 数组的含义是什么？

2. KMP 的时间复杂度是多少？

3. 如何用 next 判断循环节？

易错点

⚠️ 注意：

1. next 数组的含义
2. 匹配失败时 j 的回退
3. KMP 比暴力快很多
4. 循环节判断：n % (n - next[n-1]) == 0