跳转至

前缀函数与 KMP 算法

发现自己不会 KMP 的模板了,借此机会复习一下 KMP,顺便更深入地研究前缀函数 \(\pi\) 的应用。

写在前面

为了更方便地描述字符串相关内容,我们做出以下规定:

  1. 字符串通常用 \(S, T\) 等表示,\(c\) 通常表示一个字符,\(\Sigma\) 表示字符集;
  2. 字符串长度用 \(\left|S\right|\) 表示;
  3. 字符集大小用 \(\left|\Sigma\right|\) 表示;
  4. \(S[l..r]\) 表示 \(S[l], S[l + 1], \ldots, S[r - 1], S[r]\)
  5. 空串用 \(\epsilon\) 表示;
  6. \(S\)\(T\) 的前缀,用 \(S \sqsubset T\) 表示;\(S\)\(T\) 的后缀,用 \(S \sqsupset T\) 表示;
  7. \(S\) 的第 \(i\) 个前缀,即 \(S[1..i]\),用 \(S_i\) 表示。

特殊地,本文的字符串下标、\(\pi\) 数组下标 均从 \(1\) 开始

一些字符串有关术语的例子

对于 \(S = \mathtt{ABCBAD}\) 而言:

  1. \(\left|S\right| = 6\)
  2. \(\left|\Sigma\right| = 4\)
  3. \(S[2..4] = \mathtt{BCBA}\)
  4. \(S_4 = \mathtt{ABCB}\)

前缀函数数组

定义

对于一个字符串 \(S\),我们定义其前缀函数 \(\pi(S)\) 的值为 \(S\) 的最长相等的真前缀和真后缀的长度,即: $$ \begin{aligned} \pi(S) & = \mathop{\operatorname{argmax}}\limits_{k < \left|S\right|}\{S[1..k] = S[\left|S\right| - k + 1..\left|S\right|]\} \\ & = \mathop{\operatorname{argmax}}\limits_{k < \left|S\right|}\{S_k \sqsupset S\} \end{aligned} $$ 对于一个字符串 \(S\),我们定义其前缀函数数组 \(\pi\)\(\pi[i] = \pi(S_i)\)

\(\pi[1]\) 等于……?

特殊地,当 \(\left|S\right| = 1\)\(\pi(S) = \mathop{\operatorname{argmax}}\limits_{k < 1}\\{S[1..k] = S[2 - k..1]\\}\)

此时有 \(k = 0\) 满足 \(S[1..0] = S[2..1] = \epsilon\),故 \(\left|S\right| = 1 \Longrightarrow \pi(S) = 0\)

性质 1

\(\pi(S_i) = \pi[i] < i\)

证明

由定义知 \(\pi[i] < i\),即得证。

算法流程

  1. 根据定义,\(\pi[1] = 0\)

  2. 假设我们循环到了要求 \(\pi[i]\quad(i \ge 2)\),令 \(k \gets \pi[i - 1]\)

    \(\pi\) 数组的定义得,此时 \(S[1..k] = S[i - k, i - 1]\)

    我们现在要做的,就是从 \(\pi[1..i - 1]\) 递推到 \(\pi[i]\)

    考虑到 \(\pi\) 数组的定义,我们不断地枚举共同的前后缀(即使用 \(k = \pi[k]\) 来迭代)。

    结束这个迭代,有且仅有两种情况:\(k = 0\)\(S[k + 1] = S[i]\)


    对于前者,说明对于字符串 \(S[1..i]\),不存在任何两个真前缀与真后缀相同,\(\pi[i] = 0\)

    对于后者,说明我们找到了一个 \(k\),使得 \(S[1..k + 1] = S[i - k..i]\),根据定义,有 \(\pi[i] = k + 1\)

  3. 至此,我们求出了字符串 \(S\) 的前缀函数数组 \(\pi\)

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
#include <bits/stdc++.h>
void calcPi(char* S) {
    pi[1] = 0;
    int len = strlen(S + 1);
    for(int i = 2, k = 0; i <= len; ++i) {
        while(k > 0 && S[k + 1] != S[i])
            k = pi[k];
        if(S[k + 1] == S[i])
            ++k;
        pi[i] = k;
    }
}

正确性

引理 1(后缀重叠引理)

对于 \(x, y\) 满足 \(x \sqsupset z, y \sqsupset z\) 而言,有:

  • \(\left|x\right| \le \left|y\right|\),则 \(x \sqsupset y\)

  • \(\left|x\right| \ge \left|y\right|\),则 \(y \sqsupset x\)

  • \(\left|x\right| = \left|y\right|\),则 \(x = y\)

证明

过于显然,证明略。

设 $$ \pi^{\star}[q] = \{\pi[q], \pi^{(2)}[q], \cdots, \pi^{(t)}[q]\} $$ 其中 $$ \pi^{(i)}[q] = \begin{cases}q & i = 0 \\ \pi[\pi^{(i - 1)}[q]] & i \ge 1\end{cases} $$ 当 \(\pi^{(t)}[q] = 0\)\(\pi^{\star}[q]\) 中的序列终止。

引理 2(前缀函数迭代引理)

对任意长度为 \(n\) 的字符串 \(S\),有 $$ \forall q \in [1, n], \pi^{\star}[q] = \{k: k < q \land S_k \sqsupset S_q\} $$

证明
  • 先证明 \(\pi^{\star}[q] \subseteq \\{k:k < q \land S_k \sqsupset S_q\\}\)

    即证明 \(\forall x \in \pi^{\star}[q], x < q \land S_x \sqsupset S_q\)

    任取 \(x \in \pi^{\star}[q]\),不妨设 \(x = \pi^{u}[q] \quad (u > 0)\),下面通过对 \(u\) 的数学归纳法证明命题成立。

    (基础)当 \(u = 1\) 时,\(x = \pi[q]\),由 \(\pi\) 数组的定义可知 \(\pi[q] < q \land S_{\pi[q]} \sqsupset S_q\)

    (假设)假设当 \(u = v\)\(\pi^{v}[q] < q \land S_{\pi^{v}[q]} \sqsupset S_q\)

    (推导)则当 \(u = v + 1\) 时,\(\pi^{v + 1}[q] = \pi[\pi^{v}[q]] < \pi^{v}[q] < q\)(性质 1);\(S_{\pi^{v + 1}[q]} \sqsupset S_{\pi^{v}[q]} \sqsupset S_q\)(由性质 1 得到下标的大小关系,由引理 1 得到前缀之间的关系)

    因此 \(\forall x \in \pi^{\star}[q], x < q \land S_x \sqsupset S_q\)

  • 再证明 \(\\{k:k < q \land S_k \sqsupset S_q\\} \subseteq \pi^{\star}[q]\)

    即证明 \(\forall x \in \\{k:k < q \land S_x \sqsupset S_q\\}, x \in\pi^{\star}[q]\)

    考虑使用反证法来证明命题成立。

    假设集合 \(M = \\{k:k < q \land S_k \sqsupset S_q\\} - \pi^{\star}[q]\) 非空,\(j\)\(M\) 中的最大值。

    \(\because\) \(\pi[q]\)\(\\{k:k < q \land S_x \sqsupset S_q\\}\) 中的最大值,且 \(j \in \\{k:k < q \land S_x \sqsupset S_q\\}\)

    \(\therefore j < \pi[q], S_j \sqsupset S_q\)

    \(\because \pi[q] \in \pi^{\star}[q]\)

    \(\therefore \exists j' \in \pi^{\star}[q], \text{s.t. }j' > j\)

    \(j'\) 表示 \(\pi^{\star}[q]\) 中比 \(j\) 大的最小整数。

    \(\because \\{k:k < q \land S_k \sqsupset S_q\\} \subseteq \pi^{\star}[q]\)\(j' \in \pi^{\star}[q]\)

    \(\therefore S_{j'} \sqsupset S_q\)

    \(\because j' > j\)\(j\) 是小于 \(j'\) 的最大值

    \(\therefore S_j \sqsupset S_{j'}\)(引理 1)

    \(\pi\) 数组的定义知 \(\pi[j'] = j\)

    \(\because j' \in \pi^{\star}[q]\)

    \(\therefore j = \pi[j'] \in \pi^{\star}[q]\),与假设矛盾

    因此 \(\\{k:k < q \land S_k \sqsupset S_q\\} \subseteq \pi^{\star}[q]\)

综上所述,对任意长度为 \(n\) 的字符串 \(S\),有 \(\forall q \in [1, n], \pi^{\star}[q] = \\{k: k < q \land S_k \sqsupset S_q\\}\)

引理 3

对任意长度为 \(n\) 的字符串 \(S\),有 \(\forall q \in [1, n]\),若 \(\pi[q] > 0\),则 \(\pi[q] - 1 \in \pi^{\star}[q - 1]\)

证明

\(x = \pi[q] > 0\),则 \(x < q, S_x \sqsupset S_q\)

\(\because x > 0\),则 \(x - 1\) 有意义

\(\therefore x - 1 < q - 1, S_{x - 1} \sqsupset S_{q - 1}\)(把 \(S_x\)\(S_q\) 的最后一个字符去掉)

由引理 2 知 \(x - 1 \in \pi^{\star}[q - 1]\)

\(\therefore \forall q \in [1, n] \land \pi[q] > 0,\pi[q] - 1 \in \pi^{\star}[q - 1]\)

\(q \in [2, n]\) 定义子集 \(E_{q - i} \subseteq \pi^{\star}[q - 1]\) 为: $$ E_{q - 1} = \{k\in\pi^{\star}[q - 1]:S_{k + 1} = S_k\} $$ 则有: $$ \begin{aligned} E_{q - 1} & = \{k\in\pi^{\star}[q - 1]:S_{k + 1} = S_k\} \\ & = \{k: k < q - 1, S_k \sqsupset S_{q - 1}, S[k + 1] = S[q]\} \\ & = \{k: k < q - 1, S_{k + 1} \sqsupset S_q\} \end{aligned} $$ 因此,\(E_{q - 1}\) 是由 \(\pi^{\star}[q - 1]\) 中的值组成的、能满足 \(S_{k + 1}\)\(S_q\) 的某个后缀相等的 \(k\) 组成的集合。

推论 1

对任意长度为 \(n\) 的字符串 \(S\),有 $$ \forall q \in [2, n],\pi[q] = \begin{cases}0 & E_{q - 1} = \varnothing \\ 1 + \max\{k \in E_{q - 1}\} & E_{q - 1} \neq \varnothing\end{cases} $$

证明
  • \(E_{q - 1} = \varnothing\) 时,不存在任何一个 \(k \in \pi^{\star}[q - 1]\),使得 \(S_{k + 1} \sqsupset S_q\)

    显然此时 \(\pi[q]\) 只能为 \(0\)

  • \(E_{q - 1} \neq \varnothing\) 时,

    • \(\forall k \in E_{q - 1}, k < q - 1 \land S_{k + 1} \sqsupset S_q \Longrightarrow k + 1 < q\)

    则由 \(\pi[q]\) 的定义,\(k\) 是拓展到 \(S_q\) 的某一后缀的备选项,\(\pi[q] \ge 1 + \max\\{k \in E_{q - 1}\\}\)

    • 注意到此时 \(\pi[q] > 0\),设 \(r = \pi[q] - 1\)

    \(r + 1 = \pi[q] < q, S_{r + 1} = S_{\pi[q]} \sqsupset S_q\)

    \(\because r + 1 > 0\)

    \(\therefore S_{r + 1} = S_q\)

    由引理 3 可得 \(r = \pi[q] - 1 \in \pi^{\star}[q - 1]\)

    \(\therefore r \in E_{q - 1}\)

    \(\therefore \pi[q] - 1 = r \le \max\\{k \in E_{q - 1}\\}\)

    \(\pi[q] \le 1 + \max\\{k \in E_{q - 1}\\}\)

综上所述,当 \(E_{q - 1} \neq \varnothing\)\(\pi[q] = 1 + \max\\{k \in E_{q - 1}\\}\)

再看一次代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
#include <bits/stdc++.h>
void calcPi(char* S) {
    pi[1] = 0;
    int len = strlen(S + 1);
    for(int i = 2, k = 0; i <= len; ++i) {
        while(k > 0 && S[k + 1] != S[i])
            k = pi[k];
        if(S[k + 1] == S[i])
            ++k;
        pi[i] = k;
    }
}

接下来我们将使用循环不变式来证明上述代码的正确性。

证明
  • 初始化

    在第 4 行的迭代开始前,有 \(i = 1, k = \pi[i] = 0\),不变式成立。

  • 保持

    在每次迭代开始前,有 \(k = \pi[i - 1]\)

    • 若是第一次迭代,此等式由第 4 行保证;

    • 其余迭代均由第 9 行保证。

    接下来要证明每次迭代结束后均有 \(k = \pi[i]\) 成立。

    \(k \neq \pi[i]\),则会在第 5-8 行将 \(k\) 调整至 \(\pi[i]\)

    • 第 5 行的 while 循环遍历每一个 \(k \in \pi^{\star}[i - 1]\),直至找到一个 \(k\),使得 \(S[k + 1] = S[i]\)。(引理 2)

      • 若找不到这样的值,则在第 7 行 \(k = 0\)
      • 若找到了这样的值,此时 \(k\) 为满足条件的集合中的最大值,应将 \(\pi[i] \gets k + 1\)。(推论 1)

    第 9 行的赋值语句使得 \(k = \pi[i]\) 恒成立。

  • 终止

    \(i = n + 1\) 时,迭代终止,此时我们求出了 \(\pi[1..n]\)

    至此,算法结束。

因此,上述代码实现能正确地求出字符串 \(S\) 的前缀函数数组。

时间复杂度

不难发现,第 7-9 行代码的时间复杂度均为 \(O(n)\),唯一棘手的是第 6-7 行代码。

考虑 \(k\) 的变化,\(k\) 在第 7-8 行增加的次数不超过 \(n\) 次,即 \(k \le n\)

\(k\) 在第 6 行的操作中,因为有 \(\pi(S_i) < i\) 的性质,导致每次迭代至少使 \(k\) 减小 \(1\),即最多迭代 \(n\) 次。

综上所述,用上述方法求一个字符串的前缀函数数组的时间复杂度为 \(O(n)\)

空间复杂度

易知用此种方法求前缀函数数组的空间复杂度为 \(O(n)\)

KMP 算法

算法流程

我们举一个例子:用 \(S = \mathtt{CCFCCFMONEY}\)\(T = \mathtt{CCFCCFSB}\) 匹配。

我们定义两个指针 \(i,k\),表示 \(S[i - k..i - 1] = T[1..k]\)

我们要拓展的,就是 \(S[i]\)\(T[k + 1]\) 之间的关系。

首先我们考虑朴素算法的弊端:当你匹配到了 \(i = 8, k = 7\) 时: $$ \begin{aligned} S & = \mathtt{\color{green}CCFXCCF\color{red}M\color{black}ONEY} \\ T & = \mathtt{\color{green}CCFXCCF\color{red}S\color{black}B} \\ \text{index} & =\mathtt{123456789} \end{aligned} $$ 你发现 \(S[i] = S[8] = \mathtt{M}\),可 \(T[k + 1] = T[8] = \mathtt{S}\),我们前功尽弃,只能将 \(T\) 往右平移一格。

而且要重新开始:\(i = 1, k = 1\)。 $$ \begin{aligned} S & = \mathtt{CCFXCCFMONEY} \\ T & = \mathtt{\text{ }CCFXCCFSB} \\ \text{index} & =\mathtt{123456789} \end{aligned} $$ 显然朴素算法的时间复杂度为 \(O(nm)\)


再考虑使用前缀函数 \(\pi\) 来优化匹配的过程。

不难求出 \(T\) 的前缀数组 \(\pi[1..n] = \{0, 1, 0, 0, 1, 2, 3, 0, 0\}\)

考虑前缀数组的意义:\(T_i\) 的最长的相等的前后缀长度。

你知道了当 \(i = 8, k = 7\) 时,有 \(S[1..7] = T[1..7]\),而且 \(T[1..3] = T[5..7]\)

在上述的例子中,也就是我们可以把 \(T[1..3]\) 这个地方匹配到的 \(\mathtt{\color{green}CCF}\) 移动到 \(S[5..8]\) 去。

这样就直接节省了三次移动。


总结一下使用前缀函数 \(\pi\) 时我们的匹配过程:

  1. 使用 \(i, k\) 来表示当前 \(S[i - k..i - 1] = T[1..k]\)

  2. 如果 \(S[i] \neq T[k + 1]\),我们就用 \(\pi\) 函数来实现大幅度的跳跃;

    否则 \(k' \gets k + 1\),表示 \(S[i - k..i] = T[1..k + 1]\)

  3. \(k = m\) 时,说明找到了一个匹配 \(S[i - m + 1..i] = T[1..m]\)

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#include <bits/stdc++.h>
void KMP(char *S, char *T) {
    for(int i = 1, k = 0; i <= n; ++i) {
        while(k > 0 && T[k + 1] != S[i])
            k = pi[k];
        if(T[k + 1] == S[i])
            ++k;
        if(k == m) {
            printf("%d\n", i - m + 1); // S[i - m + 1..i] = T[1..m]
            k = pi[k];
        }
    }
}

正确性

可以证明,上述代码实现是正确的。

时间复杂度

依葫芦画瓢地使用求前缀函数数组时的摊还分析方法,不难得出 KMP 算法的时间复杂度为 \(O(n + m)\)

空间复杂度

不难发现 KMP 算法的空间复杂度为 \(O(n + m)\)

例题

  1. 「NOI2014」动物园

  2. 「POJ 1961」Period

  3. 「CF1200E」Compress Words

  4. 「POI2006」OKR-Periods of Words

写在最后

KMP

Reflect upon yourself before you judge others.

感觉前缀函数的性质非常优秀,可以有倍增 next 数组之类的神奇操作来艹标算。(大雾