Luogu5115 Check,Check,Check one two!

题意：给定长为 的字符串 。

记 为 与 的最长公共前缀长度。

记 为 与 的最长公共后缀长度。

给出常数 ，求

答案对 取模。

，字符集为小写英文字母，时限 。

---

好题。

对于 ，显然 是完全相同的，且向两侧延伸的长度是极长的。

枚举所有这样的 对应的极长串对，计算贡献。

对于一个子串 的两次出现，如果这两次出现都是极长的（即向两侧扩展后不相同），则可以贡献。

具体地，贡献值为：

首先枚举中心（即 ）在串中的位置，然后将两侧可以延伸的距离乘起来求和。

上式中唯一的变量为 ，得知 后可以 预处理。

---

对 建立 。

对于每个 节点，显然只有最长串可能产生极长串对。（其他串产生的串对都能扩展为最长串）

观察 上极长串对的结构。两个 在它们的 处才有可能产生极长串对，在更浅的祖先处则不再是极长的。

这提示我们在树上合并。

观察两个在 处相遇的 ，它们的前面已经确定不能扩展，但后面仍然有可能扩展。

于是暴力记下后方下一个字符的情况。记 表示 子树中的 下一个是 的个数。

当两组 合并时，利用 容易算出产生的极长串对。

复杂度 。 若字符集较大，使用启发式合并可以做到 。