题意

求最短的子串,满足整个字符串可以通过子串的重复覆盖得到。

分析

显然这个子串是公共前后缀。考虑用KMP解决。

对于一个前缀,考虑这个前缀所有出现位置的终点,若任意两个相邻的终点之间的差值不超过这个前缀的长度,而且这个前缀又是一个后缀的话,显然是满足要求的。

我们要求的是这样的最短前缀。

用KMP的Next数组建出Fail树,一个前缀所有出现位置的终点显然就是Fail树里这个节点为根结点的子树中的所有节点。而保证是后缀的话,就是找到节点\(n\)路径上的节点。

现在就是要解决如果结算一个子数里面相邻节点差的最大值。

我们从根往下走的时候,显然到节点\(n\)的路径是唯一的。

那么,我们其实往下走的时候,就是不断的删除节点,询问当前剩余节点的最大值。

这个步骤可以用双向链表来维护。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注