PAM 是一种高效存储字符串中所有回文子串的自动机，用于解决回文串相关问题。 虽然代码稍微长一点，但写起来比 manacher 容易很多，毕竟没有加了一堆字符再转回原串的若干上取整下取整问题。

无。或许需要一些自动机相关的理论基础。

我们用 PAM 上的一个节点来表示一个回文子串，作为 PAM 的一个状态。但回文串分奇偶两种，像 manacher 一样在每两个字符之间加分隔符是很麻烦的。因此，我们把 PAM 的状态分成两个部分，一部分存奇回文串，另一部分存偶回文串。

同理，我们把根也分为奇根和偶根。它们不表示任何字符串，只作为初始状态而存在。 因为存的是回文串，我们其实只需要对一个串记录其中一半位置的字符是什么，所以定义 PAM 上的一个点到根的路径上的字符串表示它所代表的回文串的其中一半，这一点上 PAM 与以前学过的自动机状态的定义都不同。 换句话说，对于一个点它实际表示的回文串，在 PAM 上的读法是从它开始沿着 PAM 读到根，再原路读回该点形成的字符串。这里注意如果是奇回文串，与根相连的那个字符边只读一次。

令奇根为 \(1\)，偶根为 \(0\)。那么对于 \(s=\texttt{"abaabc"}\)，建出的 PAM 如下图（省略 Fail 指针）： 每个点表示的回文串根据上文所述即可读出，例如点 \(7\) 表示 \(\texttt{c}\)，点 \(4\) 表示串 \(\texttt{aba}\)，点 \(6\) 表示串 \(\texttt{baab}\)。

在 PAM 中，每个节点同样有一个 Fail 指针。这里 \(\text{Fail}(x)\) 的定义是 \(x\) 表示的回文串的最长回文后缀的状态。（也同时是最长回文前缀，因为 \(x\) 是回文串） 对于初始状态，我们定义偶根的 Fail 指向奇根。而我们并不关心奇根的 Fail，因为任意一个长度为 \(1\) 的字符串都是回文串，奇根不可能失配。

同时，对于每个节点我们记录 \(\text{len}(x)\) 表示它实际代表的回文串长度，用于在下文 PAM 的构造中判断每个点在原串中的位置。那么对于点 \(x\)，设它在 PAM 上的父亲是 \(fa(x)\)，则有 \(\text{len}(x)=\text{len}(fa(x))+2\)。 为保证奇回文串也满足这个性质，令 \(\text{len}(1)=-1\)。

对于之前的例子，建出它的 Fail 指针就是这样的（为了减少交叉，把 \(2\) 和 \(7\) 号点换了位置）：

PAM 的构造方式是在线的，即每次添加一个字符 \(c\) 时，在原来的 PAM 基础上添加与新增字符相关的状态和转移。 假设对于一个长度为 \(n\) 的字符串 \(s\)，我们已经构造完了前 \(n-1\) 个字符，现在要加入第 \(n\) 个字符。设这个字符为 \(c\)，前 \(n-1\) 个字符最长回文后缀对应的状态是 \(now\)。 要新增的状态就是以第 \(n\) 个字符结尾，且在以前没有出现过的回文串。考虑到一个回文串前后各去掉一位还是回文串，新增的回文串前后去掉一位，一定是某个以 \(n-1\) 为结尾的回文串。 我们要找的就是以 \(n-1\) 为结尾的回文串中，前一位恰好是 \(c\) 的最长的串。发现上一次构造到的节点 \(now\) 就表示以 \(n-1\) 为结尾的最长回文串，因此我们不断令 \(now\gets \text{Fail}(now)\)，直至满足条件。设使条件满足的状态为 \(pos\)。那么以 \(n\) 为结尾的最长回文后缀就是在 \(x\) 前后各加一个 \(c\)。根据 PAM 的定义，这个状态就是 \(pos\) 通过字符 \(c\) 的边连向的儿子。

如果 \(pos\) 没有对应的儿子，代表这个回文串是新增的，我们添加一个新的状态。否则既然已经存在就不用管了。 那么对于这个新的状态，可以证明只有最长的这个回文后缀是新增的。考虑一个比它短的回文后缀，可以在最长的里面对称到一个不包括 \(n\) 的字符串，这一定是以前出现过的状态。 （如果黑的是最长回文后缀，蓝的是次长回文后缀，那显然红的和蓝的相同，也是回文串，在前面出现过。）

那么我们令新点为 \(new\)，容易得出 \(fa(new)=pos\)，\(\text{len}(new)=\text{len}(pos)+2\)。 只剩下它的 Fail 还没有求了。

发现求 Fail 指针和求最长以 \(n\) 结尾的回文后缀的本质是一样的。这次我们从 \(\text{Fail}(pos)\) 开始跳，找到第一个能在前后各加一个 \(c\) 的回文串即可。 如果到最后都没匹配到，令 \(\text{Fail}(new)=0\) 就好了。 你可能会奇怪为什么不指向奇根呢，这两个都是啥也没有。考虑这样的情况：原来字符串只有一个字符 \(\texttt{a}\)，现在变成了 \(\texttt{aa}\)。那么这个新回文串是从偶根同时也是之前的 Fail 转移过来的。如果一开始把 \(a\) 的 Fail 指向奇根就会转移不到这种情况。

看起来构建完了。

结构体定义是平凡的：

设函数 getfail(u,i) 表示从状态 \(u\) 开始查找首个前一位与 \(s_i\) 相同的回文后缀状态。