回文串和回文自动机

1 PAM 简介

1.1 PAM 的形式

PAM 是一个自动机，它的普通边组成了两棵树，fail 边组成了一棵树。

这两棵普通树分别表示主串中所有奇数长度的回文串和偶数长度的回文串，其根节点分别叫做“奇根”和“偶根”。普通边上有字母（类似 trie/SAM 的普通边，都是存 \(\sum\) 个外链，但是有一些是无效的）。一个节点代表一个回文串：考虑从其到所在根的路径上字母拼起来为 \(s_1s_2...s_k\)，那么如果这个节点在奇树上那么其表示 \(s_1s_2...s_{k-1}s_ks_{k-1}...s_2s_1\)，否则表示 \(s_1s_2...s_{k-1}s_ks_ks_{k-1}...s_2s_1\)。

由上所述一个节点表示一个良定义的串，那么其 fail 边表示代表其最长回文后缀的节点。

1.2 PAM 的构建

考虑增量构造法。令 \(lst\) 为目前加入的字符串的最长回文后缀所在节点。现在在字符串背后插入 \(x\) 字符，假设插入完这个字符之后有 \(n\) 个字符。我们维护每一个节点表示的字符串长度 \(len\)。考虑从 \(lst\) 开始不断跳 \(fail\)，直到 \(s_n = s_{n - len_{lst} - 1}\)，也就是从 \(lst\) 开始可以往左右分别加入一个字符为止，此时新的字符串的最长回文后缀就是 \(lst\) 的 \(x\) 普通边，如果不存在则需要新建。

我们记找到的这个点为 \(now\)。考虑继续从 \(fa_{lst}\) 向上跳 \(fa\) 直到 \(s_n = s_{n-len_{lst} - 1}\)。此时找到了 \(fail_{now}\)。关键的性质来了：这时候 \(fail_{now}\) 一定存在，从而也不需要继续往下找到它的最长回文后缀了。

引理 1：\(fail_{now}\) 一定存在。

引理 2：回文自动机上一定出现了所有回文串。

考虑归纳证明这两个引理的正确性。

首先我们假设上一步结束之后满足条件。

考虑引理 2 的正确性：只需要满足所有后缀回文串会在这一步内添加到 PAM。

如果引理 1 成立，那么加入最大的那个后缀回文串之后，次大的一定之前就在 PAM 中，那么引理 2 就是正确的了。

考虑引理 1：首先次大的这个串 \(xBx\) 一定在之前出现过。由于 \(xAx\) 是回文串，所以 \(xAx\) 的前 \(len_B + 2\) 个字符一定是 \(xBx\)，所以在之前就已经出现过了。其次由于归纳假设，已经出现过的串在 PAM 上。因此引理 1 成立。

从而我们证明了这两个引理。

接下来考虑奇根和偶根的参数应当怎么设置。我习惯令 \(0\) 号节点为偶根，\(1\) 号节点为奇根。由于我们希望奇根不会失配，令其 \(len = -1\) 即可。而偶根的 \(len = 0\)。接下来我们考虑如何设置他们的 fail 指针，以及正常节点一直向上跳应该跳到哪里。

这里结合一个例子来讲。考虑串 \(\mathtt {aaaaba(a)}\)。增加最后一个 \(\mathtt a\) 的时候 \(lst\) 的 \(len = 3\)，也即 \(\mathtt {aba}\)。我们接下来要跳 fail 是因为要找到一个两边都能接的上 \(\mathtt a\) 的点。在这个串里，这个点恰恰是偶根。所以我们是要在正常的回文后缀之后增加奇根和偶根作为前面全部不符合条件的备选项，而先选择偶根然后才选择奇根。因此应该令 \(fail_0 = 1\)，且正常节点的 \(fail\) 如果未定义的话应该为 \(0\)。

如何令这个想法兼容我们的算法流程？考虑 \(0\) 应该是某一个点的 \(x\) 边。考虑这个串里面 \(fail_{now}\) 是如何求出。它的普通父亲是 \(0\)，当我们跳到 \(-1\) 的时候匹配上，这时候 \(fail_{now} = edge_{1, x}\)。如果 \(edge_{1, x}\) 有值，那么 \(fail_{now}\) 应当是这个值。否则 \(fail_{now}\) 应当是 \(0\)。因此只需要令 \(edge_{1, *}\) 初始全为 \(0\) 即可。

（如上图，\(\mathtt {aa}\) 的 \(fail\) 应当为 \(\mathtt a\)，因为 \(edge_{1, a} = \mathtt a\)；如果没有值，那么应该为 \(0\)）

1.3 PAM 的正确性

性质 1：PAM 的状态数线性。

由于上一步证明了一次只会增加至多一个节点，所以显然线性状态数成立。

这个性质等价于，一个字符串的本质不同回文串个数等于其字符数。

对于空间：你只需要开 \(n + O(1)\) 个节点即可，不同于 SAM 的 \(2n +O(1)\)。

性质 2：PAM 的跳转次数为线性。

首先除了跳 fail 之外的操作显然为 \(O(n)\)。那么只需要考虑跳 fail 操作的次数即可。

跳 fail 分两步：第一步是从 \(lst\) 开始跳 fail 直到找到普通树上 \(now\) 的父亲。第二步是从 \(now\) 的父亲的 fail 开始跳 fail 直到找到 \(fail_{now}\) 的父亲。

考虑第一步的跳转次数。我们发现下一次的起点就是上一次的终点的普通儿子，儿子关系深度最多增加 \(1\)，跳一次深度减少 \(1\)，所以跳转次数为 \(O(n)\)。

考虑第二步的跳转次数。

如上图，红边是一个普通边，黑边是若干个 fail 边。绿色是第二步跳转的路径。可以直观地看出，下一次跳转的起点比上一次跳转的终点的深度更低。所以跳转次数也为 \(O(n)\)。

1.4 PAM 的运用

运用 1：求本质不同回文子串个数。

就是状态数减去奇根和偶根两个状态。

运用 2：求回文子串出现次数。

考虑某一个前缀。我们知道其最长回文后缀所在的节点，并且它如果出现了，那么它的所有 fail 祖先也会出现一次。因此我们只需要对增量构造的时候走到每一个 \(now\) 的时候对 \(dp_{now}\) 增加 \(1\)，然后某一个回文子串的出现次数就是其子树 \(dp\) 值的和。

这个做法的关键在于出现的所有回文串组成 fail 树上的一条链。这也可以套用到其他的应用上。

1.5 PAM 和 manacher 的运用场景对比

OI-wiki 上有一句话，“由于空间限制，PAM 不能完全替代 manacher。”也就是说，除了空间限制之外，PAM 完全可以替代 manacher？

回顾一下，manacher 求出了以每一个点为回文中心的时候，最长回文半径是什么。所有回文串可以被分成 \(2n\) 类，其中每一类的回文中心一致，并且回文半径连续。虽然 PAM 并没有做到这样的事情，但是目前并没有觉得这点有什么先进的地方。

而 manacher 很难求本质不同回文串为单位的信息，用上弱周期引理的话可以做到单 \(\log\)，但是 PAM 可以轻松做到线性；和 SAM 一样，知道本质不同回文串为单位的信息之后你就可以乘以它的出现次数。

P-P-Palindrome

给定 \(n\) 个字符串 \(S_1, ..., S_n\)，

一个 \(\mathtt{P-P-Palindrome}\) 定义为一个有序对 \((P, Q)\)，其中 \(P, Q\) 都是 \(S_1, ..., S_n\) 中某一个字符串的子串，并且 \(P,Q,P+Q\) 都是回文串。

计算不同的 \(\mathtt{P-P-Palindrome}\) 个数，其中两个 \(\mathtt{P-P-Palindrome}\) 不同当且仅当 \(P\) 不同或者 \(Q\) 不同。

\(1 \le n \le 10^6, 1 \le \sum |S_i| \le 10^6\)

Palindrome Partition

给定字符串 \(s\)，求有多少它的子串（连续）使得它是一个偶长度回文串或者若干个偶长度回文串的拼接。两个子串不同当且仅当它们在原串里位置不同。

\(\sum |s| \le 5 \times 10^5\)