KMP 算法堪称经典中的经典, 然而这么多年以来, 我却未能完全理解这个算法. 我对 KMP 算法掌握的程度, 是知其原理, 但写不出来.
今天打 CF, 遇到一个 KMP 的题目, 解法很好想, 代码量也不大, 我却未能在最后的 17 分钟内 AC. 痛定思痛, 痛何如哉. 今天我要用最详细的语言, 把我对 KMP 算法的理解写下来, 借此将这个算法印在我心里.
相比于朴素的匹配算法, KMP 算法的优越之处在于不会进行重复比较(或者说不会进行重复匹配).
无论哪一篇介绍 KMP 算法的文章都会提到这一点, 那么不会进行重复比较所指的究竟是什么呢?
概括的说, 这指的是在整个匹配过程中, 文本串 $T$ 的每个字符只处理一次.
注意, 这里所谓的「处理」一次不一定是只比较一次, 处理 $T[i]$ 的过程中,$T[i]$ 可能与模式串 $P$ 的多个位置上的字符进行比较.
下面来解释 KMP 算法是如何做到对文本串 $T$ 的每个字符只处理一次的.
KMP 算法的核心是 fail 数组. 先来解释此数组的名字, 为何将其命名为 fail.
想象按朴素的办法在文本串 $T$ 中匹配模式串 $P$ 的过程:
从头开始比较, 假设在第 $i$ 个字符处失配了, 也就是说 $i$ 之前都能匹配上, 但 $T[i] \ne P[i]$. 失配英文可作 mismatch, 也可称为 fail. 总之, fail 就是失配的意思. 具体地说, fail[i] 指示着「若发现文本串 $T$ 的第 $j$ 个位置和模式串 $P$ 的第 $i$ 个位置失配了, 即 $T[j] \ne P[i]$, 那么下一步 $T[j]$ 应该与 $P$ 的哪个位置上的字符相比较」. 换言之, 若 $T[j]$ 与 $P[i]$ 失配了, 下一步就比较 $T[j]$ 与 $P[\fail[i]]$. 若 $T[j] = P[\fail[i]]$ 则 $T[j]$ 处理完毕, 接着处理 $T[j+1]$, 即拿 $T[j+1]$ 与 $P[\fail[i]+1]$ 比较. 若 $T[j] \ne P[\fail[i]]$, 即 $T[j]$ 再次失配, 则再将 $T[j]$ 与 $P[\fail[\fail[i]]]$ 比较. 如此迭代, 直到 $T[j]$ 匹配成功, 或者到达边界条件, 即 $T[j]$ 与 $P[0]$ 失配, 这意味着从 $T[j]$ 往前数找不到模式串 $P$ 的前缀,$T[j]$ 亦处理完毕, 接着处理 $T[j+1]$, 将其与 $P[0]$ 比较.
上一段叙述了在求出 fail 数组之后如何用它在文本串中搜索 (或称匹配) 模式串. 接着来讲如何求 fail 数组.
首先考虑边界条件 fail[0].
如果文本串 $T$ 的某个位置 $j$ 跟 $P[0]$ 失配了, 那么 $T[j]$ 就处理完了, 接着应该比较 $T[j+1]$ 与 $P[0]$.
据此, 我们可以令 $\fail[0] = -1$, 即假想在模式串 $P$ 的首个字符 $P[0]$ 之前有一通配符 *,* 可以和任意字符匹配.
假设已经求出了 $\fail[0], \fail[1], \dots, \fail[i-1]$.
回顾 $\fail[i]$ 的定义, 在匹配过程中遇到文本串的第 $j$ 个位置与模式串的第 $i$ 个位置失配, 那么下一步应该将 $T[j]$ 与模式串的第 $\fail[i]$ 个字符比较.
不妨设想 $T[j-1]$ 与 $P[i-1]$ 失配了, 我们知道此时应比较 $T[j-1]$ 与 $P[fail[i-1]]$, 按照上面所述的方法, 不断迭代, 直到找到 $T[j-1]$ 在 $P$ 中的匹配位置, 假设这个位置是 $x$, 不难看出 $\fail[i]$ 就等于 $x + 1$, 于是我们得到了求 $\fail[i]$ 的方法.
注意到, 当文本串 $T$ 的第 $j$ 个位置与模式串 $P$ 的第 $i$ 个位置失配时, 我们有 $P[0..i-1]$ 等于 $T[j-i..j-1]$. 我们可以把求 fail 数组的过程看作是「在 $P$ 中搜索 $P$」, 即文本串 $T$ 与模式串 $P$ 相等. 求 $\fail[i]$, 我们假想「文本串的 $P[i-1]$」 与「模式串的 $P[i-1]$」"失配", 此时应将文本串的 $P[i-1]$ 与模式串的 $P[\fail[i-1]]$ 相比较, 不断迭代, 直到找到「文本串的 $P[i-1]$」在模式串中的匹配位置, 设此位置为 $x$, 那么 $\fail[i]$ 就等于 $x + 1$ .
分析至此, 我们看到, 求 fail 数组和在文本串 $T$ 中搜索模式串 $P$ 可以归结为同一个问题.
我们可以把这两个过程的共同点抽出来, 写成一个函数 int get_next(const char *P, const int *fail, const char ch, int i) . 这个函数的作用是求出「当字符 ch 与模式串 $P$ 的第 $i$ 个位置失配时, 应该将 ch 的后继字符与模式串 $P$ 的哪个位置作比较」. 这个函数的名称, 写得具体点, 应该是 get_next_when_fail_at 或者 get_next_if_fail_at.
- int get_next(const char *P, const int *fail, const char ch, int i) {
- i = fail[i];
- while (i != -1 && ch != P[i]) {
- i = fail[i];
- }
- return i + 1;
- }
有了这个函数, 求 fail 数组就很方便了.
- void get_fail(const char *P, int *fail, const int len_P) {
- fail[0] = -1;
- for (int i = 1; i <= len_P; i++) {
- fail[i] = get_next(P, fail, P[i-1], i - 1);
- }
- }
其中参数 len_P 表示模式串 $P$ 的长度.
关于 fail 数组需要特别指出的是
一, 根据 fail 数组的定义, fail 数组的下标范围是[0, len_P], 不止 [0, len_P-1]. 换言之, $\fail[i]$ 对 $i = 0, 1, 2, \dots, \mathrm{len\_P} - 1, \mathrm{len\_P}$ 都有定义.
二, 根据 fail 数组的定义, 必有 $\fail[1] = 0$, 也可以把 $\fail[1] = 0$ 和 $\fail[0] = -1$ 一并作为边界条件, 并将函数 get_fail 中的 for 循环改成从 $i = 2$ 开始. 为了简洁, 我没有这样做.
借助 fail 数组, 在文本串 $T$ 中匹配模式串 $P$ 的过程也很容易写
- int KMP_match(const char *P, const int len_P, const char * T, const int len_T, const int *fail) {
- int cnt = 0;
- for (int i = 0, j = 0; i < len_T; ++i) {
- if (T[i] == P[j]) {
- ++j;
- if (j == len_P) {
- ++cnt;
- j = fail[j];
- }
- }
- else {
- j = get_next(P, fail, T[i], j);
- }
- }
- return cnt; // P 在 T 中出现的次数
- }
值得指出的是, 上述代码并不要求模式串 P null-terminated. 如果 P 是 null-terminated 的, 即 P[len_P] == '\0', 那么上述代码的第 8 行 j = fail[j]; 可去掉.
复杂度分析
由于 get_fail 和 KMP_match 实质是相同的. 下面只详述如何分析 get_fail 的复杂度.
我们观察 fail 数组的相邻两项是如何变化的.
注意到, 从 $\fail[j-1]$ 到 $\fail[j]$, fail 值的增长是通过函数 get_next 的最后一行 return i + 1; 实现的, 增量是 1. 而函数 get_next 中的 while 循环里的 i = fail[i]; 这个语句使 i 减小(亦即使 $\fail[j]$ 的值减少), 每次至少减少 1. 所以在函数 get_fail 的执行过程中, 函数 get_next 的 while 循环中的语句 i = fail[i]; 执行至多 len_P 次.
KMP_match 的复杂度分析是类似的, 观察其中的变量 $j$ 的变化规律, 亦能得到类似的结论.
补充
许多介绍 KMP 算法的文章是从 prefix function(前缀函数)讲起的. 但我认为 fail 数组比 prefix function 更符合直觉, 从而使得整个算法容易理解与记忆. 另外 fail 数组包含着自动机的思想, 从 fail 数组很容易扩展到 AC 自动机, fail 数组有助于理解自动机理论, 从而使人容易理解其他基于自动机的算法(例如后缀自动机).
来源: http://www.bubuko.com/infodetail-2981323.html