0. 约定
字符串的下标从 \(0\) 开始。\(|s|\) 表示字符串 \(s\) 的长度。
对于字符串 \(s\)，记其每一个字符分别为 \(s_0, s_1, \cdots, s_{|s|-1}\)。
子串 \(s_l, s_{l+1}, \cdots, s_{r-1}, s_r\) 简记为 \(s[l:r]\)。特别地，若 \(l=0\)，可记作 \(s[:r]\)；若 \(r=|s|-1\)，可记作 \(s[l:]\)。
对于字符串 \(a, b\)，\(a+b\) 表示拼接操作，即将字符串 \(b\) 拼接到字符串 \(a\) 之后，构成新的字符串。
记构成的新字符串为 \(c\)，则上述拼接操作记为 \(c\gets a+b\)。
其中符号 \(x\gets y\) 表示将 \(y\) 的值赋给 \(x\)。
不论是字符还是字符串，皆不加引号。
1. 回文自动机介绍和结构
回文自动机，又称回文树，是一个能够存储字符串中所有回文子串的数据结构。
首先放一张图来感受回文自动机的总体结构。这是对字符串 \(\texttt{eertree}\)构建的回文自动机。
（eertree是回文自动机最初提出时的名字，图片来自于原论文）
可以看出，有以下几个特点：
- 回文自动机由两棵树和一堆fail指针组成。
- 一棵树的根是 \(0\)，称为偶根；另一棵树的根是 \(-1\)，称为奇根。
- 回文自动机中每个结点表示一个回文串（奇根和偶根除外）。
- 奇回文串在奇根所在树上，偶回文串在偶根所在树上（废话
- 从上往下，回文自动机中普通边的意义为在字符串两侧各加入的字符。（奇根与其儿子之间的边除外）
- fail指针指向结点所表示的回文串的最长回文真后缀的对应结点。
- 人为规定没有最长回文真后缀的fail指针指向 \(0\)，\(fail(0)=-1\)，\(fail(-1)\) 意义不大。
从本质上来说，应该有 \(fail(-1)=0\)。这样我们才能够将回文自动机定义为DFA，具体如下：
回文自动机是一个接受且仅接受某个字符串的所有回文子串的中心及右半部分的DFA。
“中心及右边部分”在奇回文串中就是字面意思，在偶回文串中定义为一个特殊字符加上右边部分。
这个定义看起来很奇怪，但它能让 PAM 真正成为一个自动机，而不仅是两棵树。
......
为了让 PAM 符合自动机的定义，可以在概念上从-1到0连一条特殊字符边，然后以-1作为起始状态。然而在代码实现里没有人会这么做。
——ouuan
原论文中定义 \(fail(-1)=-1\) 是因为原论文并没有将其视为自动机。