回文自动机
回文自动机
回文自动机与AC自动机是实现思想非常类似，可以类比。
1. 变量定义
| AC | 回文 | |
|---|---|---|
| x号节点表示的串的最长存在后缀 | x号节点表示的回文串的最长存在的回文后缀 | |
| x号节点后接字母i后所得的串 | x号节点两端接字母i后所得的回文串 |
不过为了判断回文串的存在性，要进而维护数组len表示回文串x的长。
2. 构造方法
-
首先，让节点
0 的fail 指向1 -
顺次扫描文本串中每个字符，尝试使用“上次操作后末尾最长的回文串”两边分别加
s[n] 和s[n-len[last]-1] ，假若不行，就类似于AC自动机的模式，让last 顺着fail 往上跳，直到匹配上为止。假如目前构造出的串没有出现过，就新开节点。 -
新节点的
fail 指针亦可类比AC自动机，它遵循“多重平行四边形定则”，连向u顺着fail 链往上跳，能与s[n] 构成回文的串，的s[n] 号儿子，它不可能不存在。 -
对于出现过的回文串种数，输出
tot-1 即可（空串与-1串不算）；对于出现过的回文串条数，要从后往前扫点，把它的条数加到fail[i] 上去，并逐个累加。
3. 代码
void ins(int c,int p){
for(x=y;S[p]!=S[p-l[x]-1];x=Fa[x]);
if(s[x][c]) return y=s[x][c],void();
l[s[x][c]=y=++cnt]=l[x]+2;ok[y]=ok[x];
if(x==1) return;
for(x=Fa[x];S[p]!=S[p-l[x]-1];x=Fa[x]);Fa[y]=s[x][c];
}