回文自动机

回文自动机是一种专门处理回文串问题的数据结构，于2014年于俄罗斯提出（战斗民族自动机）。事实上，对于大部分回文串问题，可以用manacher算法A掉，但是对于那些懒得想乱搞，只喜欢用暴力方法骗分的蒟蒻（对就是在说我），回文自动机是一个非常好的选择。其优秀的nlogn时间复杂度和强大的处理能力使许多需要manacher+乱搞的题变成了回文自动机裸题。

好，那么就让我们一起看一看三大有限机之一—–回文自动机的工作原理吧

1.回文自动机的前置技能

如果你了解AC自动机，那么理解fail指针部分应该不需要花费太多时间。如果你不会AC自动机，那么你需要了解KMP算法中next数组的原理

如果你什么都不知道，而且懒得去看博客，那么你可能需要背板子了（没错就是在说我）

2.回文自动机的组成

回文自动机由一颗奇回文树和一颗偶回文树构成，每个节点代表一个回文子串，节点间用fail指针相连

3.回文自动机的内部构造

(1)回文自动机的组成部分

const long long maxn=300005;
long long s[maxn],next[maxn][26],len[maxn],cnt[maxn],fail[maxn];
long long last,p,n;
char ss[maxn];

ss为输入的字符串，s记录新插入的节点，len[i]表示i回文串的长度，cnt[i]表示i回文串在字符串(ss)里出现的次数。

last是以字符串中上一个位置(即i-1)结尾的回文串编号，p是新建节点编号，n是新加入字符编号。

那么next是什么呢？看到next是不是有点熟悉？没错，它代表的就是节点i代表的回文串在两边添加字符c以后变成的回文串的编号。

（所以学好KMP很重要）

(2)回文自动机的初始化

既然回文自动机是两棵树，那么我们就需要链式前向星来建树。。。啊，不好意思走神了。

那么，还是用解释代码的方式来吧

void init(){
    p=fail[0]=1;
    last=n=0;
    s[0]=len[1]=-1;
}  

last,n不用解释吧

s[0]=-1是向字符串里加一个没有的字符，减少特判。

len[0]=0,len[1]=-1是初始化奇回文树和偶回文树的根节点长度。为什么我们把奇回文树的根节点长度设为-1呢？其实是简化之后长度为1的回文串的处理而精心构造的。（我口胡的）

p=1，因为有一个节点了(0)，fail[0]=1则是用fail指针将回文树连起来。

(3)回文自动机的构造方式+工作原理

void add(long long c){
    c-='a';s[++n]=c;
    long long cur=get_fail(last);
    if(!next[cur][c]){
        fail[++p]=next[get_fail(fail[cur])][c];
        next[cur][c]=p;
        len[p]=len[cur]+2;
    }
    last=next[cur][c];
    ++cnt[last];
}

哇，回文自动机核心竟然这~么短！惊不惊喜意不意外！

咳，说正事。这就是回文自动机的内部结构了。首先传进来一个字符，将它放进s里，编号n+1。

然后。。。诶怎么有个get_fail函数?

long long get_fail(long long x){
    while(s[n-len[x]-1]!=s[n])x=fail[x];
    return x;
}

学过ac自动机的小朋友一定对fail有很深的印象吧。事实上，回文自动机也是通过fail指针失配后回跳到上一个节点继续匹配的。get_fail函数就是判断回跳到的节点所代表的串是否为回文串，如果不是则继续跳，直到回到合法节点。

那么，当我们找出last的fail指针指向的节点（回文串）后，检查向它收尾加入c字符后形成的字符串是否已经存在。若不存在，则新建节点（节点编号p+1），该节点的fail指针指向向当前节点的fail指针指向的节点的fail指针指向的节点尾加入c字符后形成的节点（大家：你在说什么）。

这是什么呢？让我们好好想一想。用代码来说，cur是当前节点编号最大的节点的失配节点，那么，如果next[cur][c]存在，它就和last相等了。不存在，就新建节点，并将其保存在其中。然后，由于cur是个字符串，所以不能把c+cur的fail指向fail[cur]（要不然就不是奇偶回文树了），而是get_fail(fail[cur])。

然后就是加边，更新长度。最后记一下last，节点为last的数量++

当然，这样求出来的数量并非真实数量（因为大字符串可以包含小字符串），所以我们还需要count函数，倒着加一遍。

long long count(){
    for(long long i=p;i>=0;--i){
        cnt[fail[i]]+=cnt[i];
    }
}

4.回文自动机求出的结果

说了这么多，回文自动机到底是求啥的？

回文自动机最牛逼的地方就是可以求出一个字符串中所有不同种类的字符串（本质不同的字符串），以及每一种字符串出现的次数。

所以，凡是遇到回文串的题，用回文自动机扫过去，就可以将一个充满回文子串的毒瘤字符串扒的一干二净（迫真战斗民族）。

最后放个代码我就跑了（

#include<cstdio>
#include<algorithm>
#include<cstring>
const long long maxn=300005;
long long s[maxn],next[maxn][26],len[maxn],cnt[maxn],num[maxn],fail[maxn];
long long last,p,n;
char ss[maxn];
void init(){
    p=1,last=0,n=0,s[0]=-1,fail[0]=1,len[1]=-1;
}

long long get_fail(long long x){
    while(s[n-len[x]-1]!=s[n])x=fail[x];
    return x;
}

void add(long long c){
    c-='a';s[++n]=c;
    long long cur=get_fail(last);
    if(!next[cur][c]){
        fail[++p]=next[get_fail(fail[cur])][c];
        next[cur][c]=p;
        len[p]=len[cur]+2;
    }
    last=next[cur][c];
    ++cnt[last];
}

long long count(){
    for(long long i=p;i>=0;--i){
        cnt[fail[i]]+=cnt[i];
    }
}

int main(){
    scanf("%s",ss);
    long long len=strlen(ss);
    init();
    for(long long i=0;i<len;i++)add(ss[i]);
    printf("%lld",count());
}