KMP 字符串匹配

给定文本串 text 和模式串 pattern，要找出模式串在文本串中出现的位置。朴素算法会在失配时把模式串整体右移一位，重复比较已经匹配过的字符；KMP 利用模式串自身的重复结构，避免文本指针回退。

1. 前缀函数

字符串 s 的真前缀是从开头取的一段、但不包含整个字符串；真后缀是从结尾取的一段、也不包含整个字符串。pi[i] 表示子串 s[0..i] 的最长相等真前缀和真后缀的长度。

以 s = "aabaa" 为例：

子串 最长相等真前后缀 pi[i]
a 不存在 0
aa a 1
aab 不存在 0
aaba a 1
aabaa aa 2

因此前缀函数为 [0, 1, 0, 1, 2]。

2. 如何在线性时间构造前缀函数

处理位置 i 时，令 j = pi[i - 1]，它表示当前已知的候选前后缀长度。如果 s[i] 与 s[j] 不同，就把 j 回退为 pi[j - 1]，尝试更短、仍有可能匹配的边界；匹配后将长度加一。

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> prefixFunction(const string& s) {
    int n = static_cast<int>(s.size());
    vector<int> pi(n, 0);
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }
        if (s[i] == s[j]) ++j;
        pi[i] = j;
    }
    return pi;
}

每次回退都跳到一个更短的已知边界，因此整个构造过程为 O(n)。

3. 用前缀函数匹配

匹配时，i 扫描文本串，j 表示模式串当前已匹配的长度。失配时不移动 i，而是用 pi[j - 1] 缩短已匹配部分。若 j == pattern.size()，说明找到一次匹配；随后回退 j，继续寻找可能重叠的匹配。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> findMatches(const string& text, const string& pattern) {
    vector<int> positions;
    if (pattern.empty()) return positions; // 本例约定空模式串不返回匹配

    vector<int> pi = prefixFunction(pattern);
    int j = 0;
    for (int i = 0; i < static_cast<int>(text.size()); ++i) {
        while (j > 0 && text[i] != pattern[j]) {
            j = pi[j - 1];
        }
        if (text[i] == pattern[j]) ++j;
        if (j == static_cast<int>(pattern.size())) {
            positions.push_back(i - j + 1); // 0-based 起始下标
            j = pi[j - 1];
        }
    }
    return positions;
}

完整示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

vector<int> prefixFunction(const string& s) {
    int n = static_cast<int>(s.size());
    vector<int> pi(n, 0);
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) ++j;
        pi[i] = j;
    }
    return pi;
}

vector<int> findMatches(const string& text, const string& pattern) {
    vector<int> positions;
    if (pattern.empty()) return positions;
    vector<int> pi = prefixFunction(pattern);
    int j = 0;
    for (int i = 0; i < static_cast<int>(text.size()); ++i) {
        while (j > 0 && text[i] != pattern[j]) j = pi[j - 1];
        if (text[i] == pattern[j]) ++j;
        if (j == static_cast<int>(pattern.size())) {
            positions.push_back(i - j + 1);
            j = pi[j - 1];
        }
    }
    return positions;
}

int main() {
    string text, pattern;
    cin >> text >> pattern;
    vector<int> pi = prefixFunction(pattern);
    vector<int> positions = findMatches(text, pattern);
    for (int position : positions) cout << position << ' ';
    cout << '\n';
    for (int value : pi) cout << value << ' ';
    cout << '\n';
}

匹配和前缀函数构造的时间复杂度分别为 O(n + m) 和 O(m)，额外空间为 O(m)。示例输出匹配起点使用 0-based 下标；若题目要求 1-based 下标，输出时加一。

4. 常见疑问

  • 失配时查的是已匹配前缀的边界 pi[j - 1]，不是失配字符自身的前缀值。
  • 匹配成功后不能简单把 j 清零，否则会漏掉重叠匹配；应回退到 pi[j - 1]。
  • 空模式串的定义因题目而异。本文约定返回空结果，使用时按题意调整。
  • std::string 按字节处理字符。若要按 Unicode 字符匹配，需要先把文本解码成字符序列。

练习：洛谷 P3375：KMP 字符串匹配。提交前请按题目要求调整匹配下标和前缀数组的输出格式。