广义 KMP 以及其扩展（Broad Sense Kmp）

一月 07, 2024

写在前面：这篇文章不介绍普通的 KMP 算法，主要介绍这个算法的一些扩展。

Update：其实是针对于一些字符串算法的扩展并且对字符串和普通数字序列的一些性质的挖掘和分析、解决。

KMP

众所周知，我们认为下面这份代码是 KMP 算法：

for(int i=2,k=0;i<=n;i++){
	while(k&&s[i]!=s[k+1]) k=ne[k];
	if(s[i]==s[k+1]) k++;
	ne[i] = k;
}

实际上它是 MP 算法，Knuth 则在 MP 算法的基础上提出了优化，同时改变了 $\text{next}$ 数组的含义。

但是如果判断一个串是不是包含另外一个串，则还是判断是否有 $\text{next}_i = m$（$m$ 为另一个串的长度）。

如下所示：

for(int i=1,k=0;i<=n;i++){
	while(k&&s[i]!=s[k]) k=ne[k];
	i++,k++;
	if(s[i]==s[k]) ne[i]=ne[k];
	else ne[i]=k;
}

前面那份代码可以求出来最小循环节，但是后面那份代码就不可以，而且前面那份代码如果在字符串末尾增减字符，再次跑 while 循环的时候时间会爆，即不满足单次复杂度严格低于 $O(n)$。

后面这份代码不可以求最小循环节，但是增减字符后，再跑 while 循环的时候时间就爆不了（至少目前卡不掉）。

但是这并不是文章的重点。

广义 KMP

众所周知，KMP 是跑子串匹配的算法。

普通的 (K)MP 算法，是指找到 $S$ 的一个前缀等于后缀的字符串的最大长度，这个字符串的长度必须小于 $S$ 的长度。

我们则可以尝试找到字符串的一些性质：

字符串的等于判断具有传递性，即如果 $a=b,b=c$ 那么 $a=c$。
如果 $a=b$ 那么对于任意 $a_{l \sim r} = b_{l \sim r}$ 。
字符串的每个元素一定只有 $26$ 种。

我们需要发挥想象力，不妨把字母换成数字，再重新定义任意两个序列相同的条件，满足上面两条性质，我们就可以根据 (K)MP 来找 $b$ 这个序列在 $a$ 中出现的次数以及位置，特别的，如果不要求最长的前后缀长度，我们甚至可以运用 KMP 算法来支持末尾添加数字删除数字的操作。

例 1

比如这道题：

序列 $a$ 和序列 $b$ 相同，当且仅当对于所有 $a_i = a_j$，$b_i = b_j$；否则 $b_i \ne b_j$（$j<i$），求 $b$ 在 $a$ 中出现了多少次。

我们可以发现这个规定满足上面两条性质，那么可以修改一下 KMP 的代码，使得时间复杂度在 $O(n \log n)$ 以内。

比较好的做法是对于每个 $a_i$ 找出前面第一个与它相同的数字，记录一下他们之间的距离为 $a’_i$，$b$ 数组同理，如果 $a’=b’$ 那么 $a=b$。（如果找不到，那么距离为 $-1$ 即可，只需要不与可能出现的距离相同就可以）

于是我们直接判断即可，在 (K)MP 的算法执行过程当中：

for(int i=2,k=0;i<=n;i++){
	while(k&&s[i]!=s[k+1]) k=ne[k];
	if(s[i]==s[k+1]) k++;
	ne[i]=k;
}

如果 $s_i=s_{k+1}$ ，那么有一个隐含的条件就是 $s_{1 \sim k}=s_{i-k \sim i-1}$。

相当于我们在跑 (K)MP 的时候，只需要判断新加进去的数与之前加进去的数的关系就可以了。

对于这道题来说，如果 $a_{1 \sim k}=a_{i-k \sim i-1}$，那么我们需要判断 $a_{k+1}$ 加到前面一个子串末尾和 $a_i$ 加到后面的子串末尾相不相同就可以了。

把他们分别距离之前在这个串里面与他们的值相等的数找出来，计算距离就可以了。

那么模式串和文本串匹配也是这样的一个道理。

所以算法的时间复杂度为 $O(n \times \text{check 的时间复杂度})$，在这里总时间复杂度为 $O(n)$，因为不需要更多的信息，同时可以扩展到在末尾添加删除的操作。

广义 KMP 及其扩展

我们发现，运用了广义 KMP，那么就可以解决一些比较难以解决的问题。

类似于上面两个例子，如果没有这个广义 KMP 几乎上无法做出来，甚至可以加上求最长的前缀等于后缀的问题，然而我们还有更多的东西可以扩展：

AC 自动机，Z 函数等与 KMP 有关的算法。

对于 Z 函数的构建，我们依然可以采用这种方法；但是 AC 自动机仅接受 $26$ 的字符，还不如直接用暴力。

因此，最直接的地方是用在 Z 函数上。

Z 函数的运用和 KMP 的运用差不多，此处就不再赘述了，大概也是运用到了字符串的一些性质。

例 2

承袭例 1 中 $a=b$ 的条件，对于给定的序列 $c$ 的每个 $1 \le i \le n$，找到最大的一个 $k$，使得 $i+k-1 \le n$ 且 $c_{1 \sim k}=c_{i \sim i+k-1}$。

很显然，把 Z 函数构建过程中移动左右端点的判断条件改成之前的条件就可以了。

时间复杂度依然为这个算法时间复杂度乘上 $\text{check}$ 的时间复杂度。

最后输出 Z 函数的值即可。

其它字符串相关扩展

这里则主要介绍另外一种字符串相关的算法 manacher。

manacher 也是用于求解回文串的问题，我们依然可以把这个方法加到 manacher 的移动左右端点上面。

例 3

承袭例 1 中 $a=b$ 的条件，对于给定的序列 $c$ 的每个 $1 \le i \le n$，找到最大的一个 $k$，使得 $i+k-1 \le n,i \ge k$ 且 $c_{i-k+1 \sim i}=c_{i+k-1 \sim i}$。（后一个字符串是倒过来的）

这就是一个模板的 manacher 题目，那么我们依然加上 $\text{check}$ 函数就可以了。

时间复杂度依然为这个算法时间复杂度乘上 $\text{check}$ 的时间复杂度。

甚至可以在现有 manacher 题目上做出进一步修改，此处的例题仅为注重展示此算法，而不是为了难住读者。

总结

我们此处就是把一个字符串改变成了一个序列，并且重载了字符串的 $=$ 运算符，使得序列满足了上述算法的一些性质来解决较为困难的问题。

然后与上述算法相关的自动机们和所有靠移动指针判断是否相等（一次常数以内）的算法，都可以适用到这个方法。（AC 自动机则在条件允许的情况下可以用这个方法，回文自动机同理）

但是我们的后缀相关数据结构就不能使用这种方法，因为它们主要解决的是字典序排名的问题，与字符串匹配没有太大关系，因此不行。

对于这篇文章，旨在对 KMP 的一些相关习题进行总结，比如很多题目都可用这个方法解决，而我们也可以用这种方法出一些质量较高的题目。

比如：[COCI2011-2012#4] KRIPTOGRAM。

即使很多题目都可以用奇奇怪怪的 hash AC，但是这种方法也不失于一种正确性稳定的算法。

综上，这是我在学习 KMP 时候的一些想法，如有不足请大家多多指出，笔者也好修改这篇文章，以免误导更多的读者。

—The End—

查看评论