字符串算法三连击

本文是介绍KMP算法的运用

KMP算法

给定两个字符串 $S, T$ ，询问 $T$ 是否在 $S$ 中出现过，如果出现过要给出所有出现的位置，时间复杂度 $O\left(\left|S\right| + \left|T\right|\right)$

KMP算法的核心是Next数组

Next 数组

定义 $next$ : $String \rightarrow Int$ 函数，它表示一个字符串的最长的严格前缀等于对应长度后缀的长度

$next(abacaba) = 3$ ，因为前缀和后缀都是 $aba$ ，并且没有更长的了

$next(aaaaa) = 4$ ，因为前缀和后缀都是 $aaaa$ ，注意原串 $aaaaa$ 也同时是前缀和后缀，但我们要求是严格前缀

$next(abcde) = 0$ ，因为不存在一个前缀等于对应长度后缀

对于一个字符串 $S$ ，我们定义它的 $next$ 数组的第 $i$ 项为 $S$ 前 $i$ 个字符构成的前缀的 $next$ 函数
对于字符串 $abacaba$ 来说，它的 $next$ 数组是： $next : 0, 0, 1, 0, 1, 2, 3$

算法主体

如果要求 $T$ 是否在 $S$ 中出现过，先求 $T$ 的 $next$ 数组（假设已经求好）

记录两个指针 $i, j$ ，表示当前匹配到字符串 $S$ 的 $i$ 位置，匹配到字符串 $T$ 的 $j$ 位置

如果 $S_{i + 1} = T_{j + 1}$ ，该字符匹配成功， $i = i + 1, j = j + 1$

如果 $S_{i + 1} \neq T_{j + 1}$ ，匹配失败， $j = next_j$ （ $j$ 移动到可行的最后一个位置）

如果 $j$ 到末尾，说明已经匹配成功，输出匹配位置，并 $j = next_j$ ，表示开始准备下一次匹配

求Next数组

核心思想：自己与自己错位做匹配

考虑已知 $next_1, next_2 ..... next_p$ ，求 $next_{p + 1}$

如果 $S_{p + 1} = S_{next_p + 1}$ ，那么 $next_{p + 1} = next_p + 1$
如果不相等？判断 $S_{p + 1} = S_{next[next_p]} + 1]$

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

KMP在题目中的应用

下面是一些 $KMP$ 的题目

周期串判断

题目

给定一个字符串 $S$ ，问 $S$ 是否是周期串，也就是是否有 $S = AAA · · · A$ 这样的形式。如果有找出最短的循环节，否则输出 $−1$ 。 $|S| ≤ 10^5$

题解

考虑周期串有什么性质：如果 $S = A_k$ （ $k$ 个 $A$ 连在一起），那么 $A_{k−1}$ 既是 $S$ 的前缀也是 $S$ 的后缀，也就是 $A_{k−1}$ 的长度应该等于 $next(S)$

如果 $|S| − next(S)$ 是 $n$ 的一个约数的话，根据前缀后缀的相等关系我们可以断定 $S$ 必然是周期串，又由于 $next(S)$ 的最大性质，前 $|S| − next(S)$ 个字符一定就是最短循环节。否则 $S$ 必然不是一个周期串。

CEOI 2011 Match

题目

给出一个长度为 $n$ 的排列 $S$ （ $1$ 到 $n$ 的所有数都出现一次），并给出一个长度为 $m$ 的序列 $T$ ，求 $T$ 的所有满足如下条件的子串：

该子串长度为 $n$
该子串的第 $i$ 个数恰为整个子串的第 $S_i$ 大的数

$n ≤ 10^5; m ≤ 10^5$

题解

修改一下 KMP 算法中， $S_{i + 1} = T_{j + 1}$ 中等号的定义.

定义 $s_i$ 是 $S_i$ 在 $S$ 的前 $i$ 位中的排名。
如果 $T$ 的某个子串 $t$ 中， $t_i$ 的排名恰好是 $s_i$ ，就认为 $t_i = S_i$ 。

可以用树状数组在将 $T$ 离散化后 $O(\log n)$ 判定。

Q: 为什么这样做是对的呢？

考虑当前匹配的指针后移一位，不会影响之前的匹配结果

实际上就是把排名对应相等的字符串看成是等价的字符串做匹配

End.

「字符串算法」KMP算法