所谓回文自动机，就是一个能用来做回文问题的自动机。
Part 0. 待解决的问题
问一个串的本质不同回文串个数。
需要一个线形做法。
以下为 abbaabba 的回文自动机。
Part 1. 构造
考虑建一个树形结构。也就是回文树。
-
增量法构造，在 \(s[0\sim i-1]\) 的回文树增加一个 \(s[i]\)，只会增加一个节点。
证明：考虑新产生的最长回文子串，所有新产生的回文串，都是最长回文子串的回文后缀。会发现这些新产生的都能一一对应翻转以后的前面插入过的短串。于是只会增加一个最新回文子串的节点。
于是本质不同回文子串的数目是 \(O(n)\) 的。
你会发现答案就是自动机点数 - 2.
- fail 指针
和 AC 自动机类似，它的 fail 指针对应最长可匹配的前后缀，PAM 的 fail 则定义为最长回文后缀的位置。
设 \(s[0\sim i-1]\) 的最长回文子串在 PAM 上的节点为 \(x\)。
我们考虑 \(i - 1 - len[x]\) 和 \(s[i]\) 是否匹配，如果匹配，我们就知道这个是最长的了。
考虑 \(s[i]\) 的最长回文子串是 \(s[i-len[i]+1\sim i]\)，我们要求 \(s[i-len[i]+2 \sim i - 1]\) 是满足 \(s[i-1-len[x]] = s[i]\) 的最长回文子串，不然和新加的最长是他矛盾。
如果匹配了， 我们就让新节点的 fail 指向匹配的点 \(x\)。
- 细节
- fail[0] = 1，因为例如插入 \(aabbc\) 时，\(c\) 这个东西他是匹配不了啥的，但是能在奇数根连一条边，形如 \(1\to c\)。
如果是 \(aabbcc\)，他是有机会形成 \(cc\) 这样的在 \(0\) 这个根的串，我们需要让他尝试一下。 - 要分类讨论新点是否存在，如果存在，那么直接让 当前节点去到 这个存在的点。（自动机嘛，维护的是当前 \(s[0\sim i]\) 的最长回文子串对应节点）。
不存在就新建节点。注意先更新 fail，方法是一直跳 \(fail[x]\) 的 fail，然后更新新点的 \(fail\)。然后设 \(siz[i]\) 表示自动机上 \(i\) 结尾的回文子串数目。
\(siz[x] = siz[fail[x]] + 1\)，表示 \(x\) 比他最长回文后缀多一个回文子串。
要注意先更新 \(fail[x]\)，在更新 fail[x] 的回文树fail[++idx] = tr[gfail(fail[y], i)][s[i] - 'a'], tr[y][s[i]-'a'] = idx;。
这个很牛逼，插入 abbbc。比如说我在插入 \(b\) 时这么写。
插入 b 时，cur 在 2 号点，我们 fail[cur] 在 1 号店，\(y = gfail(fail[cur], i) = 1\)，如果已经新建了 \(tr[y][s[i]]\)，那么这时 fail[idx] 会指向 idx。（tr[y][s[i]] = idx）。
还有一个问题，为啥是从 fail[cur] 开始跳。
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef double db;
#define ep emplace_back
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define fout freopen("out.out","w",stdout);
#define fin freopen("in.in","r",stdin);
#define DE {cerr << "QAQ" << endl;}
#define dd(x) cerr << #x" = " << x << endl;
inline int read() {
int x=0, v=1,ch=getchar();
while('0'>ch||ch>'9') {
if(ch=='-') v=0;
ch=getchar();
}while('0'<=ch&&ch<='9') {
x=(x*10)+(ch^'0');
ch=getchar();
}return v?x:-x;
}
const int MAX = 5e5 + 5;
char s[MAX];
int fail[MAX],idx=1,tr[MAX][26],len[MAX],siz[MAX];
int gfail(int x,int i){
while(i-len[x]-1<0||s[i]!=s[i-len[x]-1]) x=fail[x];
return x;
}
signed main() {
fin;
scanf("%s", s);
int n=strlen(s);
fail[0]=1; len[1]=-1;
int x=0,lastans=0;
for(int i=0;i<n;++i){
if(i) s[i]=(s[i]-97+lastans)%26+97;
int y=gfail(x,i);
if(!tr[y][s[i]-'a']){
fail[++idx] = tr[gfail(fail[y], i)][s[i] - 'a'];
tr[y][s[i]-'a'] = idx;
len[idx]=len[y]+2;
siz[idx]=siz[fail[idx]]+1;
}
x=tr[y][s[i]-'a'];
// printf("%d ", lastans=siz[x]);
}
return 0;
}