字符串

yzy4090 · 2023-07-18 11:53:17 · 个人记录

字符串本质上就是多了点数位的数字。反过来，数字就是少了点字母的字符串。

KMP 模式匹配

引入

KMP 模式匹配可以对于两个字符串 A,B，在 O(|A|+|B|) 的时间复杂度下判断 A 是否是 B 的子串，并求出 A 在 B 中每次出现的位置。
（有基于哈希的做法：先预处理出前缀哈希值，然后枚举 B 的每个位置，检查 B 的一个子串与 A 的哈希值是否相同。这个做法的时间复杂度也是线性的，但无法获得更多信息，因为哈希时已经将字符串模糊化为一个数字了。此处不详细介绍）
容易想到暴力做法，时间复杂度为 O(|A||B|)。它的主要问题是每次失败后都要重新进行匹配。
KMP 模式匹配则解决了上述问题。它的主要思想是，在每次失败后，根据一定的信息得出下次从开始匹配的特定位置，从而节约时间。如图：

可以发现，当暴力还在计算 P_1 与 T_2 的关系时（此处下标从 1 开始），KMP 算法已经从第一轮枚举中知道 P_{1-2}=T_{3-4}，并且 P_1\ne T_2，所以 KMP 可以直接从 P_3 和 T_5 处开始比对。那么如何做到知道接下来应该比对哪里呢？这就是 next 数组要做的事情了。

步骤

KMP 算法分为如下两步：

1. 对 A 自我匹配，求出 next 数组，其中 next_i 表示 A 中以 i 结尾的非前缀子串与 A 的前缀能够匹配的最长长度。
2. 对 A 和 B 匹配，求出 f 数组，其中 f_i 表示 B 中以 i 结尾的子串与 A 的前缀能够匹配的最长长度。

这个算法看似治标不治本，因为暴力算 next 数组的时间复杂度还是 O(|A|^2) 的。但是 next 数组决定了下次应该回退到哪里，具体来说是回退到失配位之前最长公共前后缀对应的前缀后一位的地方。如图：

当发现 \tt c 与 \tt a （\tt a 也可以是模式串 P 的 P_3）失配后，KMP 知道 \tt beabe 的最长公共前后缀（不包括自身）是 \tt be，所以下次从 \tt be 后的 \tt a 开始比对。

在匹配前后缀时，如果扩展失败，就让指针 j 跳回 next_j，直至 j=0；否则指针 j 加 1。更新 next_i 的值，它的值即为 j。代码如下：

for(int i=2,j=0;i<=nd;i++){
    while(j>0&&d[i]!=d[j+1])j=Next[j];
    if(d[i]==d[j+1])++j;
    Next[i]=j;
}