KMP

首先我们要知道 \(\text{KMP}\) 是一个经典的字符串匹配算法。

最标准的问题形式是：

给定一个主串（\(\text{text}\)）\(T\)，长度为 \(n\)；再给定一个模式串（\(\text{pattern}\)）\(P\)，长度为 \(m\)。

我们想知道：

\(P\) 是否在 \(T\) 中出现过；如果出现过，出现在哪些位置，或者至少找到第一次出现的位置。

例如：

主串：ababcabcacbab

模式串：abcac

我们希望判断 abcac 是否是主串的一个子串，并找到它的起点下标。

这类问题叫做单模式串匹配（\(\text{single pattern matching}\)）。

朴素匹配

如果要解决这一类问题，最直接并且暴力的想法就是枚举模式串在主串中的起点，然后逐个字符比较。

也就是说，假设模式串要从主串的第 \(i\) 位开始匹配，那么我们就检查：

\(T[i]\) 和 \(P[1]\) 是否相等。
\(T[i+1]\) 和 \(P[2]\) 是否相等。
\(T[i+2]\) 和 \(P[3]\) 是否相等。
\(\cdots\)
\(T[i+m-1]\) 和 \(P[m]\) 是否相等。

如果全部相等，那么就找到了一个匹配；否则我们换下一个起点开始继续试。

关于时间复杂度，显然是 \(O(nm)\)，因为外层最多枚举 \(n-m+1\) 个起点，内层每次最多比较 \(m\) 个字符，显然这样很慢。

KMP的本质

\(\text{KMP}\) 的核心本质是，失配之后如何利用我们已经比较过的信息，避免大量重复比较。

其中失配，指的是在我们尝试匹配的过程中，某个位置没有匹配上，也就是出现了 \(T[i] \neq P[j]\) 的情况。

我们考虑这样的一组串：

主串：aaaaaaaaab
模式串：aaaab

考虑一下如果暴力匹配会发生什么？

第一次我们从主串的第一个位置开始，我们会发现连续的四个 \(a == a\)，之后出现了 \(a \neq b\)，失配了。

然后我们把模式串向右移动一下，从主串的第二个位置开始匹配，结果依然是连续的四个 \(a == a\)，之后出现了 \(a \neq b\)，失配了。

不难发现，很多操作被重复进行了很多次。我们似乎发现了什么很诡异的事情，暴力做法是把模式串向后移动一位，然后从头开始比较。但是我们明明已经知道很多字符之间的相等关系了，难道这些信息完全没用吗？

当然不是。

而 \(\text{KMP}\) 的想法就是：

既然模式串的前 \(j\) 个字符已经匹配成功了，那么失配之后，模式串其实并不需要从头开始，我们需要找到一个「仍然可以进行」匹配的位置。

这就是 next 函数要做的事情。

失配后我们到底去哪？

这是 \(\text{KMP}\) 最核心的一步。

假设我们已经匹配了 \(j\) 个字符，也就是：\(P[1..j]= T[i-j+1..i]\)，而现在第 \(j+1\) 个字符失配了。我们要探索的问题就是，我们要让模式串移动多少，才能让之前已经匹配的信息不白费？

既然当前主串的末尾是：\(T[i-j+1..i]\)，而它又和模式串的前缀 \(T[1..j]\) 相等。

那么我们希望在模式串内部，找到一个长度尽可能大的前缀，它同时也是 \(P[1..j]\) 的后缀。也就是找最大的 \(k < j\)，满足：\(P[1..k]=P[j−k+1..j]\)。

为什么这个东西有意义？

因为这意味着：虽然第 \(j+1\) 位失配了，但前面匹配成功的那一段里面，尾部还有一部分可以继续当作「新的开头」。这就避免了从头重新比较。

这样说可能比较抽象，我们来看一个例子：

我们假设模式串 \(P = ababac\)，假设某一个时刻，我们已经把前五个字符匹配好了，也就是已经匹配了： \(P[1..5] = ababa\)。

结果在下一位的时候失配了，这个时候我们要做的事情不是重新开始，而是去观察一下之前已经匹配成功的 ababa 这一段有没有什么东西可以复用。

当前的情况是：

主串: ... a b a b a b ...
模式:     a b a b a c

仔细观察这个例子，你或许就能够理解我前面所说的：前面匹配成功的那一段里面，尾部还有一部分可以继续当作「新的开头」

主串: ... a b a b a b ...
模式:         a b a b a c

你会发现，模式串开头的 aba，正好依旧能和主串末尾那段 aba 对上。所以我们不用重新从模式串第 \(1\) 位开始重新尝试，而是当前已经匹配长度从 \(5\) 变成 \(3\)。

术语

这里要先统一几个术语。

对于一个字符串 \(S\)：

前缀：从开头取若干个字符得到的串；
后缀：从结尾取若干个字符得到的串；
真前缀：不等于整个串本身的前缀；
真后缀：不等于整个串本身的后缀。

如果一个字符串既是某串的前缀，又是它的后缀，那么这个串通常称为该串的一个 \(\text{border}\)。

而这个 \(\text{border}\)，就是我们的 \(\text{next}\) 函数要求的东西。

next 函数

我们采用一种非常常见、也最便于理解的定义：

\(\text{next}[i]\) 表示字符串 \(P[1..i]\) 的最长真前后缀的长度。

形式化一点的说法是：

\[ \text{next}[i] = \max \{ k \mid k < i,P[1..k] = P[i-k+1..i] \} \]

注意是“最长真前后缀”，所以不能取整个串自己。

我们来举个简单的例子：

假设模式串 \(P\) 为 \(ababaca\)，我们来求每一个位置的 \(\text{next}\)。

\(i=1\) 时，我们考虑 \(a\) 这一段：

真前缀：空串
真后缀：空串
最长公共部分长度：\(0\)

没有相同的部分，因此 \(\text{next[1]} = 0\)。

\(i=2\) 时，我们考虑 \(ab\) 这一段：

真前缀：\(a\)
真后缀：\(b\)

显然没有相同的，因此 \(\text{next[2]} = 0\)。

\(i=3\) 时，我们考虑 \(aba\) 这一段：

真前缀：\(a,ab\)
真后缀：\(b,ba\)

最长相同的是 \(a\)，因此 \(\text{next[3]} = 1\)。

\(i=4\) 时，我们考虑 \(abab\) 这一段：

真前缀：\(a,ab,aba\)
真后缀：\(b,ba,bab\)

最长相同的是 \(ab\)，因此 \(\text{next[4]} = 2\)。

\(i=5\) 时，我们考虑 \(ababa\) 这一段：

最长真前后缀是 \(aba\)，因此 \(\text{next[5]} = 3\)。

\(i=6\) 时，我们考虑 \(ababac\) 这一段：

没有非空真前后缀相同，因此 \(\text{next[6]} = 0\)。

\(i=7\) 时，我们考虑 \(ababaca\) 这一段：

最长真前后缀是 \(a\)，因此 \(\text{next[7]} = 1\)。

综上所述：\(\text{next} = [0,0,1,2,3,0,1]\)

next 函数有什么用

这一步非常关键。

假设当前已经匹配了模式串前 \(j\) 个字符：\(P[1..j]=T[i−j+1..i]\)。

在下一位出现了失配：\(T[i+1] \neq P[j+1]\)。

那么根据 \(\text{next}[i]\) 的定义，我们可以知道 \(P[1..\text{next}[j]]=P[j−\text{next}[j]+1..j]\)。

而又因为 \(P[1..j]=T[i−j+1..i]\)。

所以模式串长度为 \(\text{next}[j]\) 的那个后缀，其实也正好等于主串结尾那一段。

这说明失配后，模式串不必退回到开头，只需要把当前已匹配长度从 \(j\) 改成 \(\text{next}[j]\) 即可。

这就是 \(\text{KMP}\) 的跳转逻辑。

于是我们的代码初具雏形：

for (int i = 1, j = 0; i <= n; i++) {
    while (j > 0 && text[i] != pattern[j + 1]) {
        j = next[j];
    }
    if (text[i] == pattern[j + 1]) {
        j++;
    }
    if (j == m) {
        // 找到一次完整匹配
        // 起点是 i - m + 1
        j = next[j];
    }
}

观察这个代码不难发现，在运行过程中，\(i\) 永远只向前走，永远不后退。而 \(j\) 只在失配的时候通过 \(\text{next}\) 回跳。

如何求解 next

这又是 \(\text{KMP}\) 的另一个核心问题。

如果我们为了求 \(\text{next}[i]\)，又对每个前缀暴力枚举所有长度，那复杂度还是会很高。所以 \(\text{KMP}\) 的第二个关键在于， \(\text{next}\) 数组本身也可以在线性时间内求出来。

按定义，\(\text{next}[i]\) 是 \(P[1..i]\) 的最长真前后缀长度。

那暴力求法就是：

枚举 \(k=i-1,i-2,\cdots,1\)
判断 \(P[1..k]\) 是否等于 \(P[i-k+1..i]\)
找到最大符合的 \(k\)

显然，这样求每个 \(\text{next}[i]\) 可能要 \(O(i^2)\)，总复杂度会达到 \(O(m^2)\)。

关键观察

现在考虑前缀：\(P[1..i-1]\)。

假设我们已经知道了：\(\text{next}[i-1] = j\)。

这说明：\(P[1..j] = P[i-j-1+1..i-1] = P[i-j,i-1]\)。

而现在我们要求 \(\text{next}[j]\)，也就是给这个末尾加上一个 \(P[i]\) 之后，最长的真前后缀变成多少。

比较好想的是，我们先看看 \(P[j+1]\) 是否和 \(P[i]\) 相等。如果相等的话那么自然有 \(\text{next}[i] = j + 1\)。

问题是如果不相等怎么办？那就说明原来的最长的 \(\text{border}\) 无法继续延长了。于是我们去考虑一下次长的 \(\text{border}\)。而这个次长的 \(\text{border}\) 长度恰好是 \(\text{next}[j]\)。

也就是说，如果失配的话，我们直接让 \(j = \text{next}[j]\)。再去尝试 \(P[j+1]\) 是否和 \(P[i]\) 相等，如果还不行的话就继续跳。直到 \(j = 0\)，或者我们找到了一个相等的位置。

于是我们可以写出这样的代码：

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

KMP 流程

有了 \(\text{next}\) 数组之后，匹配主串就非常简单了。

我们设：

\(i\) 表示当前处理到主串的位置；
\(j\) 表示当前已经匹配了模式串前多少个字符。

那么在我们每次处理 \(\text{text}[i]\) 的时候会有如下状况：

第一种情况就是匹配成功了，也就是 \(\text{text}[i] = \text{pattern}[j+1]\)，那么我们就让 \(j = j+1\)，表示我们成功多匹配了一位。

第二种情况是失配，如果 \(\text{text}[i] \neq \text{pattern}[j+1]\)。那么根据之前的分析，我们不能让 \(i\) 回退，也不能让 \(j\) 归零，而是应该 \(j = \text{next}[j]\)，然后继续尝试比较 \(\text{text}[i]\) 和新的 \(\text{pattern}[j+1]\)。

也就是：

while (j > 0 && text[i] != pattern[j + 1]) {
    j = next[j];
}

第三种情况就是找到了一组完成匹配，如果某一个时刻出现了 \(j = m\) 的情况。

说明模式串全部都匹配完了，于是我们找到了一个子串的出现位置 \(i-m+1\)，那么为了继续寻找后面的子串，我们令 \(j = \text{next}[j]\)，继续寻找下一个位置即可。

于是我们可以写出这样的代码：

vec

href="#__codelineno-5-1">// 返回模式串在主串中所有出现的位置（1-based） tor<int> KMP(string &text,string &pattern) { int n = text.size() - 1; // text[1..n] int m = pattern.size() - 1; // pattern[1..m] vector<int> next = calcNext(pattern); vector<int> pos; for (int i = 1, j = 0; i <= n; i++) { while (j > 0 && text[i] != pattern[j + 1]) { j = next[j]; } if (text[i] == pattern[j + 1]) { j++; } if (j == m) { pos.push_back(i - m + 1); j = next[j]; } } return pos; }

时间复杂度分析

最后我们来进行对 \(\text{KMP}\) 时间复杂度的分析，显然这个分析可以分为两部分，一个是求 \(\text{next}\) 函数的部分，另一个是匹配的复杂度。

对于求 \(\text{next}\) 时的复杂度：

for (int i = 2, j = 0; i <= m; i++) {
    while (j > 0 && pattern[i] != pattern[j + 1]) {
        j = next[j];
    }
    if (pattern[i] == pattern[j + 1]) {
        j++;
    }
    next[i] = j;
}

在这段代码中：

\(i\) 从左到右总共只走 \(m-1\) 次；
\(j\) 每次失配会沿着 \(\text{next}\) 不断回退；
\(j\) 增加的总次数不超过 \(m\)；
\(j\) 减少的总次数也不会超过它增加的总次数。

因此总复杂度是 \(O(m)\)。

匹配主串时同理：

\(i\) 只会从左到右扫一遍，共 \(n\) 次；
\(j\) 虽然会回退，但总回退次数是受总增加次数约束的；

因此总复杂度是：\(O(n)\)。

综上所述，\(\text{KMP}\) 的总复杂度理应是 \(O(n+m)\)。

日志

本页面创建于 2026/03/27 17:16