KMP 应用

next 树

可以说 KMP 算法的精髓就在于失配时通过 next 指针快速重新匹配。对于字符串中的第 $i$ 个位置,$\text{next}_i$ 的意义是 $s[1,i]$ 中除本身之外的同时为其前后缀的子串的最大长度。

[NOI2014] 动物园

对于一字符串,定义 $\text{num}_i$ 为其同时为不相交的前后缀的子串的最大长度。

给定一长度为 $n$ 的字符串 $s$ , 求 $\prod_{i=1}^n\text{num}_i+1$

$T\leq5,n\leq10^6$

这道题目中的 num 数组其实是对 KMP 中的 next 数组的条件进行了限制,也就是说某些符合 next 数组的子串可能因为进一步的限制(不能重合)而不再适用。很明显的是:某个位置不断沿着失配指针走,所经过的每个位置都满足“除本身之外的同时为其前后缀的子串”的限制,而为了保证其不能重合,只要这一子串的长度不大于原串长度的一半即可。

容易想到将 next 指针看成边,那么所有的指针就形成了一棵以 $0$ 号节点为根的树。

我们在这棵树上 dfs , 用一个 stack 记录当前节点到根的路径信息,然后在上面二分即可得到答案。

3670.cpp

逆向模拟 KMP 算法

字符串大师

一个串 $T$ 是 $S$ 的循环节,当且仅当存在正整数 $k$ ,使得 $S$ 是 $T$ 重复 $k$ 次的字符串的前缀。给定一个长度为 $n$ 的仅由小写字符构成的字符串 $s$ ,对于字符串 $s$ 中的每一个前缀 $i$, 给出其最短循环串的长度 $\text{per}_i$ , 求满足条件的字典序最小的字符串。

$n\leq10^5$

发现所谓的 $\text{per}_i$ 其实与 $\text{next}_i$ 有关,即 $\text{per}_i=i-\text{next}_i$ , 于是就可以求出要求的串的 next 数组。

那么问题就变成给定 next 数组还原出字典序最小的字符串,考虑两种情况:

  • $\text{next}_i=0$ , 根据充分性要求,$i-1$ 位置上以及其所有先前的匹配位置上的字符与此处不同。
  • $\text{next}_i\neq0$ , 根据必要性要求,此处的字符必须与 $\text{next}_i$ 处的相同。

时间复杂度 $O(\sigma n),\sigma\text{ 为字符集大小}$

4794.cpp