这题不是回文自动机的板子么……为啥没人用回文自动机写啊……

蒟蒻就大言不惭的来讲一讲这玩意儿好了->广告

前言

刚学完manacher就来学回文自动机……

感觉好像（板子）也不是很难（背）？

前置知识：Manacher（也不一定非要因为和这个没啥关系），知道自动机是个啥以及怎么建

简述

回文树和回文自动机指的是同一个东西

是由某西伯利亚人于2014夏发明的

这东西主要是用于计数，计算回文串的个数以及种类啥的

建树

图我就不放了（太乱了放了也看不懂），要看图的话可以去这位大神的blog里看一下->这里

不过个人感觉看文字描述应该就会了……吧……

首先，回文树里有两棵树，分别记录长度为奇数和偶数的回文串

每个节点代表一个回文串，记录转移x，表示如果在这个回文串前后都加上字符x形成的回文串是子节点的子串

然后每一个节点记录一个fail指针，指向这个回文串的最长后缀回文串

然后我们考虑建树，假设已经建好了串s[1...i-1]，要把字符s[i]插入这棵树

那么每一次只会把s[1...i]的最长后缀回文串加进树里。

证明：（抄这里的）

我们设后缀回文i是最长后缀回文k的子串，那么i肯定关于k的回文中心有一个对称串j，由于k本身是对称的，所以j和i是相同的，那么j已经被加入到回文树中，所以i不必再加入

然后就没问题了。我们设最长回文后缀为k，加入字符c，那么如果可以，最长回文后缀会变成ckc

然而如果k之前的字母不是c怎么办？这个时候fail指针就派上用场了。我们用fail维护每一个节点的最长后缀回文，如果k不行，我们看看k的最长后缀回文是否可行（就是看k的最长后缀回文的前一个字母是否等于c），然后就这样一直跳fail指针直到找到为止（如果一直没有找到会跳到根节点，下面再说）

然后如何维护fail呢？我们只要找到了当前节点的最长回文后缀然后记录一下就就好了

然后字符要接在之前的串的后面，记录一下last表示上一个串的节点

然后注意特殊处理两个根节点，0代表长度为偶数的后缀的根，1代表长度为1的后缀的根，我们令fail[0]指向1，len[1]=-1，然后令s[0]=-1（或任何一个不在原串中出现的字符）（len代表这个节点的串长）

就比如说如果跳的时候一直找不到回文怎么办？这个时候这个节点就单独形成一个回文串，那么我们在判断s[i-len[x]-1]==s[i]的时候，因为len[1]=-1，所以必定会停止，那么就不用担心会无限跳下去了

然后来几道题吧

洛谷P3649 [APIO2014]回文串

这就是一个板子，顺便记录一下出现次数就好了

然后该有的注解都会写在代码里

//minamoto
#include<cstdio>
#include<cstring>
#define ll long long
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
const int N=3e5+5;
char s[N];
int n,p,q,fail[N],cnt[N],len[N],tot,last,ch[N][26];
ll ans;
inline int newnode(int x){
    //建立一个新节点，长度为x 
    len[++tot]=x;return tot;
}
inline int getfail(int x,int n){
    //跳fail指针知道找到后缀回文为止 
    while(s[n-len[x]-1]!=s[n]) x=fail[x];
    return x;
}
int main(){
    scanf("%s",s+1);
    //一堆乱七八糟的初始化 
    s[0]=-1,fail[0]=1,last=0;
    len[0]=0,len[1]=-1,tot=1;
    for(int i=1;s[i];++i){
        s[i]-='a';
        //找到可以回文的位置 
        p=getfail(last,i);
        if(!ch[p][s[i]]){
            //如果有了转移就不用建了，否则要新建 
            //前后都加上新字符，所以新回文串长度要加2 
            q=newnode(len[p]+2);
            //因为fail指向的得是原串的严格后缀，所以要从p的fail开始找起 
            fail[q]=ch[getfail(fail[p],i)][s[i]]; 
            //记录转移 
            ch[p][s[i]]=q;
        }
        ++cnt[last=ch[p][s[i]]];
    }
    for(int i=tot;i;--i)
    cnt[fail[i]]+=cnt[i],cmax(ans,1ll*cnt[i]*len[i]);
    printf("%lld\n",ans);
    return 0;
}

洛谷P4287 [SHOI2011]双倍回文

我们肯定要先建出回文自动机的

然后如果是枚举每一个节点暴跳fail指针肯定得T

那么我们对于每一个节点记录一个trans[i]，表示小于等于它长度一半的节点

这个可以在建自动机的时候顺便求出来，具体看代码

然后对每一个节点判断长度是否模4为0且trans[i]的长度是它的一半就好了

//minamoto
#include<cstdio>
#include<cstring>
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
const int N=500005;
int fail[N],ch[N][26],cnt[N],len[N],trans[N];
int n,m,tot,last,p,q,ans;
char s[N];
inline int newnode(int x){
    len[++tot]=x;return tot;
}
inline int getfail(int x,int n){
    while(s[n-1-len[x]]!=s[n]) x=fail[x];return x;
}
void build(){
    for(int i=1;s[i];++i){
        int x=s[i]-'a';
        p=getfail(last,i);
        if(!ch[p][x]){
            q=newnode(len[p]+2);
            fail[q]=ch[getfail(fail[p],i)][x];
            ch[p][x]=q;
            if(len[q]<=2) trans[q]=fail[q];
            else{
                int tmp=trans[p];
                while(s[i-1-len[tmp]]!=s[i]||(len[tmp]+2)*2>len[q]) tmp=fail[tmp];
                trans[q]=ch[tmp][x];
            }
        }
        cnt[last=ch[p][x]]++;
    }
}
int main(){
//  freopen("testdata.in","r",stdin);
    scanf("%d",&n);
    scanf("%s",s+1);
    s[0]=-1,fail[0]=1,last=0;
    len[0]=0,len[1]=-1,tot=1;
    build();
    for(int i=tot;i>=2;--i) cnt[fail[i]]+=cnt[i];
    for(int i=2;i<=tot;++i)
    if((len[trans[i]]<<1)==len[i]&&len[i]%4==0) cmax(ans,len[i]);
    printf("%d\n",ans);
    return 0;
}

洛谷P4762 [CERC2014]Virus synthesis

先建一个回文自动机，然后记dp[i]表示转移到i节点代表的回文串的最少的需要次数

首先肯定2操作越多越好，经过2操作之后的串必定是一个回文串，所以最后的答案肯定是由一个回文串+不断暴力添加得来，那么答案就是min(ans,dp[i]+n-len[i])

然后对于一个串i，如果它在前面和后面加上一个字母可以形成回文串j，则dp[j]=dp[i]+1

为啥嘞？我们可以假设在形成i的之前一步把这个字母加上去，执行2操作后就可以变成j了

然后我们可以fail指针找到最长的回文串x满足len[x]<=len[i]/2，那么dp[i]=min(dp[i],dp[x]+1+len[i]/2-len[x])（先暴力填好一半，剩下的用2操作）

然后可以用队列记录状态，保证转移至有序的

至于怎么找x，我们可以直接在建自动机的时候顺便求出来，就是多跳几次。这个看代码好了

//minamoto
#include<cstring>
#include<cstdio>
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
const int N=2e5+5,M=5;
char s[N];int dp[N],len[N],fail[N],ch[N][M];
int trans[N],last,p,q,str[N],tot,ans,n,qu[N];
int val[105];
inline int newnode(int x){
    len[++tot]=x;memset(ch[tot],0,sizeof(ch[tot])*5);return tot;
}
inline int getfail(int x,int n){
    while(s[n-len[x]-1]!=s[n]) x=fail[x];return x;
}
inline void init(){
    val['A']=0,val['T']=1,val['C']=2,val['G']=3;
    s[0]=-1,fail[0]=1,last=0;
    len[0]=0,len[1]=-1,tot=1;
    memset(ch[0],0,sizeof(int)*5),memset(ch[1],0,sizeof(int)*5);
}
void ins(int c,int i){
    p=getfail(last,i);
    if(!ch[p][c]){
        q=newnode(len[p]+2);
        fail[q]=ch[getfail(fail[p],i)][c];
        ch[p][c]=q;
        if(len[q]<=2) trans[q]=fail[q];
        else{
            int tmp=trans[p];
            while(s[i-1-len[tmp]]!=s[i]||(len[tmp]+2)*2>len[q]) tmp=fail[tmp];
            trans[q]=ch[tmp][c];
        }
    }
    last=ch[p][c];
//    printf("%d\n",last);
}
int main(){
//    freopen("testdata.in","r",stdin);
    int T;scanf("%d",&T);
    while(T--){
        scanf("%s",s+1);
        init(),ans=n=strlen(s+1);
        for(int i=1;i<=n;++i) ins(val[s[i]],i);
        for(int i=2;i<=tot;++i) dp[i]=len[i];
        int h=1,t=0;qu[++t]=0,dp[0]=1;
        while(h<=t){
            int u=qu[h++];
            for(int i=0;i<4;++i){
                int x=ch[u][i];
                if(!x) continue;
                dp[x]=dp[u]+1;
                int y=trans[x];
                cmin(dp[x],dp[y]+1+len[x]/2-len[y]);
                cmin(ans,dp[x]+n-len[x]);
                qu[++t]=x;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

妈耶我感觉我整个人都自动机了……