回文自动机

        回文自动机,就像AC自动机一样,他采取字典树来储存状态集合,也像AC自动机是KMP 算法与字典树结合一样,回文自动机就是manacher算法和字典树结合的新算法。
        在回文自动机里面,状态指的是,以字典树上所表示的字符串的逆序串的以末端字符镜像 对称后得到的新串,简单说,baab在字典树上为root->a>b,cacaacac在字典树上为root->a->c->a->c,想像根就是对称中心,往儿子走就意味着,在 对称中心两端加上同样的数字。当然这样子是无法表示奇数回文的,所以我们设立两个根就可以了。当然,一个串的回文自动机,储存了这个串的所有回文 子串
        回文自动机的状态转移的依据是回文,举个例子,如下图,如果黑色串代表以黄色字符为结尾 的最长的回文串,红色串代表黑色串的最长真后缀回文串,(定义:若回文串a为某串b的真后缀,则a为b的真后缀回文串,定义:若后缀a为某串b的后缀且 a!=b,则a为b的真后缀)当我们在黑串后面加上一个绿字符形成新串的时候,(姑且叫他黑绿串)回文自动机中的节点会发生什么样的变化呢?显然增加了 某些新的回文串,但是我们考虑这样一个事实,如果我们把黑绿串的最长后缀回文串加入到自动机中以后,我们就把黑绿串新增的所有回文串都可以被回文自动机 所表示,证明类似于manacher算法,请自行证明。
        下面来讨论如何把它加进去。我们假设粉色字符刚好是是红色串前的一个字符,如果粉色字符和绿色 字符为同一个字符的时候,我们可以肯定,黑绿串的最长真后缀回文串就是粉色字符+红串+绿色字符。此刻我们只需要新增一个节点了。如果他们不相等的话,重复 我们对黑串的算法与红串之上即可解决。
        然后我们来考虑新增节点的所表示的回文后缀的最长真后缀回文串,我们重复使用上一段的算法,即可找 到。

大体思路就是这样子,详细细节见代码。
struct palindrome_tree{
    static const int maxn=1.2e5+5;
    int trans[maxn][26],len[maxn],suf[maxn],num[maxn];
    //字典树一样,len代表回文长度,suf指向回文后缀,类似于fail指针,num是最长后缀的数量,经过calc之后是后缀数量
    int last,cnt;//last是上一个回文后缀,cnt是所有节点数

    int new_node(int _len,int _suf,int _num){//长度,后缀,数量
        for(int i=0;i<26;i++)trans[cnt][i]=0;
        len[cnt]=_len;
        suf[cnt]=_suf;
        num[cnt]=_num;
        return cnt++;
    }

    void ini(){
        cnt=0;
        int root_even=new_node(0,1,0);//=1
        int root_odd=new_node(-1,1,0);//=0
        last=root_odd;
    }

    int query_longest_palindrom(){
        int ret=1;
        for(int i=0;i<cnt;i++){
            ret=max(ret,len[i]);
        }
        return ret;
    }

    void build(char*s){//s是要建立回文自动机的字符串,下标从1开始
        int len=(int)strlen(s+1);
        for(int i=1; i<=len; i++)extend(s,i);
        calc();
    }

    void extend(char*s,int cur){
        int w=s[cur]-'a';//当前结点的值
        int p=last;//上一次匹配到的回文后缀
        while( s[cur-len[p]-1] != s[cur]) p=suf[p];
        //现在p结点的cur儿子,要么是匹配成功的最长非自身回文后缀,要么是自身这一个字符

        if(!trans[p][w]){//如果此回文后缀未出现过,要创建节点
            int v=suf[p];//我们来找他的suffix link回边,
            while( s[cur-len[v]-1] != s[cur] )v=suf[v];
            //此时意味着找到了suffix link 是v的儿子
            trans[p][w]=new_node(len[p]+2,trans[v][w],0);
        }

        last=trans[p][w];//这一次匹配到的回文后缀
        num[last]++;
    }


    void calc(){
        for( int i=cnt-1; ~i; i-- )num[suf[i]] += num[i];//结点创建顺序保证了suf[i]<i
    }

};