回文自动机（PAM）
zac2010
·
·
题解
定义
回文自动机（回文树），一种有限状态自动机，一种可以存储一个串中所有回文子串的高效数据结构。可以简单高效地解决众多与字符串回文相关的问题。
记号与约定
下文中，s 是一个长为 n 字符串，s' 为 s 的倒串（翻转后的串），s[l,r] 是 s 的一个子串（下标从 1 开始）。
特殊情况见上下文说明。
一些性质
引理 1.1：一个回文串 s 的 \text{border} 必定是一个回文串。
引理 1.2：一个回文串 s 的所有回文后缀必定是它的 \text{border}。
证明 1.1：
-
钦定一个 s 的 \text{border} 为 s[n-i+1,n]。
-
根据 \text{border} 的性质，s[1,i]=s[n-i+1,n]；根据 s 作为回文串的性质，s[1,i]=s'[n-i+1]。故而有 s[n-i+1,n]=s'[n-i+1,n]，而它恰好是回文串的定义。
证明 1.2：可以把引理 1.1 的证明方法倒回去。
引理 2：对于一个字符串 s，它本质不同的回文子串一定是以某个点结尾的、最长的那个回文串。
证明 2：考虑反证。假设本质不同的回文子串是以某个点结尾的，但不是最长的回文串，那么根据引理 1.2 以及 \text{border} 的性质（s 的 \text{border} 的 \text{border} 也是 s 的 \text{border}），它必定已被统计过了。
引理 3：s 的本质不同的子串个数不超过 n 个。
证明 3：根据引理 2 可得。
结构
不难注意到按照传统的 $\text{Trie}$ 树，已经难以去方便地处理回文串了。
故而考虑 $\text{Trie}$ 树的变形：
* 初始时有两个节点，它们所代表的串一个长度为 $0$（用于处理偶回文），一个长度为 $-1$（用于处理奇回文）。
* 对于一个节点连出的边权 $c$ 的边，就等价于在当前节点所代表的串两边各加上一个字符 $c$。
$\text{fail}$ 树自然也跟着有了变化：
* 对于一个节点的 $\text{fail}$ 指针，它指向的是当前节点的最长回文后缀。
* 其中为了后续处理方便，我们让串长为 $0$ 的节点 $\text{fail}$ 指向串长为 $-1$ 的节点。
## 构建方式
我们采用地构建方法是逐个插入。逐个插入一般有两种：首端/末端插入。
考虑末端插入字符 $c$：
1. 以 $i-1$ 结尾的最长回文子串为开始，一直跳 $\text{fail}$ 指针，直到跳到一个合法的节点或者不能再跳了。
“合法”的定义：一个节点是合法的当且仅当它所代表的串是合法的，一个串是合法的当且仅当位于它左边的字符是 $c$，这样就可以形成一个以新插入字符结尾的回文串。
2. 判断当前跳到的节点是否是合法的节点。若是合法的节点，那就插入一个新节点，同时维护一下它的信息。不是就不插入。
* Note：会发现，对于为什么要像介绍 $\text{PAM}$ 结构时提到的那样：“让串长为 $0$ 的节点 $\text{fail}$ 指向串长为 $-1$ 的节点”，现在已经有了答案。
假设跳 $\text{fail}$ 指针时，一直跳都没有找到合法的节点，且最后落到了串长为 $0$ 的那个节点上。若那个串长为 $0$ 的节点也是不合法的，这种情况显然是没法插入一个新节点，而实际上它应该插入一个长为 $1$ 的串。
再考虑首端插入。根据引理 $1.2$，字符串的最长回文后缀等价于字符串的最长回文前缀，故而首端插入和末端插入如出一辙。
## 代码实现
```cpp
#include <bits/stdc++.h>
#define L(i, a, b) for(int i = a; i <= b; i++)
#define R(i, a, b) for(int i = a; i >= b; i--)
using namespace std;
const int N = 5e5 + 10;
int n, ans; char s[N];
struct PAM{
int n, tot, lst, s[N];
struct P{int t, len, f, c[26];} a[N];
PAM(){tot = 1, s[0] = 26, a[0].f = 1, a[1].len = -1;}
int getfail(int x){
while(s[n - a[x].len - 1] != s[n]) x = a[x].f;
return x;
}
void ins(int d){
s[++n] = d; int p = getfail(lst);
if(!a[p].c[d]){
a[++tot].len = a[p].len + 2;
a[tot].f = a[getfail(a[p].f)].c[d];
a[tot].t = a[a[tot].f].t + 1;
a[p].c[d] = tot;
}
lst = a[p].c[d];
}
} p;
int main(){
scanf("%s", s + 1), n = strlen(s + 1);
L(i, 1, n){
p.ins((s[i] - 97 + ans) % 26);
ans = p.a[p.lst].t, printf("%d ", ans);
}
return 0;
}
```