跳到主要内容

AcWing 831. KMP 字符串

本节目标

用零基 nxt 长度在主串不回退的条件下找出模式串全部出现位置。

这道题属于匹配与字典树中的单模式匹配：在主串中找出模式串的全部零基起点，重叠出现也必须保留。

查看 AcWing 原题

题意与约束​

输入依次给出模式串长度、模式串、主串长度和主串。输出模式串在主串中每个出现位置的零基下标，并以空格分隔；没有匹配时输出空行。

朴素思路与瓶颈​

朴素做法从主串每个可能起点重新比较模式串。遇到大量相同前缀时，同一段字符会被重复比较，例如主串含有许多 abab... 而模式串也以 abab 开头时。最坏情况下总比较次数为 O(nm)。

nxt 的精确定义与失配回退​

本题的 nxt[index] 是模式串 pattern[0..index] 的最长相等真前缀和真后缀的长度。例如模式串为 ababaca 时：

index:  0 1 2 3 4 5 6
字符:    a b a b a c a
nxt:    0 0 1 2 3 0 1

其中 nxt[4] = 3，因为前缀 aba 和 ababa 的后缀 aba 相等。它不是“下一个跳转下标”：当已经匹配 matched 个字符后失配，下一次仍尝试比较的模式串位置是长度所对应的位置；实现写作 matched = nxt[matched - 1]。

主串指针始终向右。每次失配只缩短 matched，直到当前字符可以继续匹配或回到零。完整匹配后记录 index - matched + 1，再令 matched = nxt[matched - 1]，于是像 aa 在 aaaa 中的 0、1、2 这样的重叠结果不会丢失。

代码实现​

C++ 的 buildNext 和 kmpSearch 都是纯核心函数：前者构建零基长度数组，后者接收主串、模式串和 nxt 返回所有起点。Python 的 build_next、kmp_search 保持同一分工。只有各语言入口读取输入并输出空格分隔的结果。

C++17
#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<int> buildNext(const string& pattern) {
    vector<int> nxt(pattern.size());
    int matched = 0;

    for (int index = 1; index < static_cast<int>(pattern.size()); index++) {
        while (matched > 0 && pattern[index] != pattern[matched]) {
            matched = nxt[matched - 1];
        }
        if (pattern[index] == pattern[matched]) {
            matched++;
        }
        nxt[index] = matched;
    }

    return nxt;
}

vector<int> kmpSearch(
    const string& text,
    const string& pattern,
    const vector<int>& nxt
) {
    vector<int> starts;
    int matched = 0;

    for (int index = 0; index < static_cast<int>(text.size()); index++) {
        while (matched > 0 && text[index] != pattern[matched]) {
            matched = nxt[matched - 1];
        }
        if (text[index] == pattern[matched]) {
            matched++;
        }
        if (matched == static_cast<int>(pattern.size())) {
            starts.push_back(index - matched + 1);
            matched = nxt[matched - 1];
        }
    }

    return starts;
}

int main() {
    int patternLength;
    string pattern;
    int textLength;
    string text;
    cin >> patternLength >> pattern >> textLength >> text;

    const vector<int> nxt = buildNext(pattern);
    const vector<int> starts = kmpSearch(text, pattern, nxt);
    for (int index = 0; index < static_cast<int>(starts.size()); index++) {
        if (index > 0) {
            cout << ' ';
        }
        cout << starts[index];
    }
    cout << '\n';
    return 0;
}

复杂度分析​

  • 预处理 nxt 的时间复杂度为 O(m)。
  • 扫描主串的时间复杂度为 O(n)，主串指针不回退。
  • 额外空间复杂度为 O(m + k)，其中 k 是匹配位置数量；最坏情况下为 O(m + n)。

易错点​

  • 将 nxt 存成跳转下标，而不是当前前缀的相等真前后缀长度。
  • 构建 nxt 或失配回退时访问 matched - 1 前没有确认 matched > 0。
  • 完整匹配后把状态清零，漏掉重叠出现。
  • 输出一基位置，或没有匹配时仍输出额外内容。

模式迁移​

固定模式串在多段文本中连续匹配时，可以保留上一段结束时的 matched；多个模式串需要同时匹配时，则转向 Aho-Corasick 自动机。两者都延续了 KMP 的原则：让失配后的状态复用已经证明相等的前缀。