题解 P3426 【[POI2005]SZA-Template】

SamariumPhosphide · 2020-06-20 07:12:09 · 题解

首先考虑，这个印章肯定是原串的一个 \text{Border}，因此一定在失配树上，根节点到编号为 \text{len} 的节点的路径上的一点。

而怎么样的路径是合法的呢？对于 一个 \text{Border}，\text{pre}(s,i) ，怎么样才能让它是合法的印章，显然它要通过连接拼出原串。而我们考虑每一个印章的结束位置，设这个结束位置为 j 那么一定满足 \text{pre}(s,i) 为 \text{pre}(s,j) 的 \text{Border}，也就是在失配树中 i 的子树中。

那么我们考虑每个这样的节点，如果有两个节点之间距离 >i 那么就会发现这两个印章之间必然会出现空隙，不能拼接完成。而如果距离 \leq i 那么一定可以拼成。

综上，我们总结出了这个印章串 \text{pre}(s,i) 需要满足的性质：

• 对于所有 j 满足 \text{pre}(s,i) 为 \text{pre}(s,j) 的 \text{Border}，即在其子树中，经过排序后相邻的最大距离不能超过 i。

那么只需要维护最大距离即可。首先把从根节点到 \text{len} 节点之间的路径打上标记。

考虑从根节点开始，每次把在下一次统计的子树以外的东西全部删掉，使用双向链表维护最大值即可，\mathcal O(n)。如果不能理解，可能参考代码更容易理解一些。

Code Here