M_sea的博客

M_sea的博客

A Mengbier

题解 P3435 【[POI2006]OKR-Periods of Words】

posted on 2019-03-31 15:17:04 | under 题解 |

$\mathrm{KMP}$ +阅读理解


首先翻译一下题目:

  • 如果存在串 $B$ ( $B$ 可以为空) ,使得 $A=PB$ ,那么称 $P$ 是 $A$ 的前缀。
  • 如果 $A\neq P$ 并且 $P$ 是 $A$ 的前缀,那么称 $P$ 是 $A$ 的 $\mathrm{proper}$ 前缀。
  • 如果 $Q$ 是 $A$ 的 $\mathrm{proper}$ 前缀,并且 $A$ 是 $QQ$ 的前缀,那么称 $Q$ 是 $A$ 的周期。
  • 如果 $Q$ 是 $A$ 的所有周期中长度最大的那个,那么称 $Q$ 是 $A$ 的最大周期。特殊的,如果 $A$ 不存在周期,那么 $A$ 的最大周期为空串。
  • 给出串 $S$ ,求 $S$ 的所有前缀的最大周期长度之和。

显然,如果前缀 $i$ 存在一个长为 $j$ 的公共前后缀,那么它就会有一个长为 $i-j$ 的周期。

$j$ 可以通过暴跳 $nxt$ 得到,然后要周期最长的话,也就是要求出最小的 $j$ 。

于是直接暴跳到 $nxt[j]=0$ 的 $j$ 处就行了。

这样子的话可以卡成 $O(n^2)$ ,考虑优化。

把每个前缀 $i$ 的答案存下来,这样子跳的时候就可以直接用,然后就是 $O(n)$ 的了。

具体实现及细节见代码