====== Palindrome Series ======

前置知识：PAM。

文中可能会用到的记号如下：

  * $|S|$：字符串 $S$ 的长度；
  * $\mathrm{per}(S)$：字符串 $S$ 的周期集合；
  * $\mathrm{minper}(S)$：$\mathrm{per}(S)$ 的最小值。

===== Border Series =====

首先不加证明地介绍一些 border 理论的引理，以便于之后集中使用。具体证明可以参考文末提及的资料，这里仅做记录。

> **引理 1（Weak Periodicity Lemma）** 若 $p, q \in \mathrm{per}(S)$，且 $p + q \leq |S|$，则 $\gcd(p, q) \in \mathrm{per}(S)$。

> **引理 2** 若 $p = \mathrm{minper}(S) \leq \dfrac {|S|}2$，则对任意 $x \in \mathrm{per}(S)$，有 $p \mid x$。

> **引理 3** 串 $S$ 所有长度 $\geq \dfrac {|S|}2$ 的 border 长度构成一个等差数列。

由引理 3 可以知道，串 $S$ 的 border 长度可以拆分为 $O(\log |S|)$ 段等差数列，只要不断对串 $S$ 中长度 $< \dfrac {|S|}2$ 部分的 border 递归使用引理 3 即可。

===== Palindrome Series =====

现在考虑回文树上 border 的情况。

> **引理 4** 串 $S$ 的后缀 $T$ 是回文串，当且仅当 $T$ 为 $S$ 的 border。

这说明了对回文串的 border 都是回文串，同时再递归使用引理 3，可以发现一个回文串的 border 同样可以拆成 $O(\log |S|)$ 段等差数列，同时这些 border 还是回文串。

这个有什么用？如果能够快速维护每段等差数列上的信息，那就可以在 $O(\log |S|)$ 的时间内枚举出 $S$ 的所有回文串后缀，进而实现一些 DP 操作。

===== 例子 =====

（虚晃一枪）（后略）

===== 参考资料 =====

  - 《子串周期查询问题的相关算法及其应用》- 陈孙立，国家集训队 2019 论文集
  - [[https://zhuanlan.zhihu.com/p/92874690|字符串科技：Palindrome Series - Calabash]]
  - [[https://www.cnblogs.com/yyf0309/p/9452065.html|Codeforces 932G Palindrome Partition - 阿波罗2003]]