[JSOI2013] 快乐的 JYY 题解

众所周知，jyy的故事将要结束了 （好吧，应该还会有故事的）。

纯纯回文自动机裸题，那回文自动机模版题在哪里，点这里。

那回文自动机又是什么，看下面。

回文自动机，也称回文树，是用来解决一些 manacher 算法不容易解决的回文串的问题，比如求解字符串 $s$ 中以第 $i$ 个字符结尾的回文串的个数。当然它还可以用于求解本质不同的回文子串的数目，所有的回文子串的数目，其复杂度也都是 $O(n)$ 的，其中 $n$ 是字符串的长度。

而回文自动机本质上就是两棵树，一棵树上挂着长度为奇数的回文串，另一棵树上挂着长度 为偶数的回文串，$0$ 代表偶数长度的根，$1$ 代表奇数长度的根。我们利用一个回文串去掉两头之后还是一个回文串的性质把所有的回文串都存储在树上。树上的每个节点都代表着一个字符串。

好了，不多说了，贴代码！

CODE:

#include<bits/stdc++.h> 
using namespace std;
const int N=50005;
struct str{
    int son[27];
    int cnt;
    int fail;
    int len; 
}s[2][N];
int S[N],last,p,n;
int new_node(int X,int x){//加入一个长度为x的点 
    s[X][p].len=x;
    return p++;
}
void init (int X){
    p=0;n=0;last=0;
    new_node(X,0);new_node(X,-1);
    S[n]=-1;
    s[X][0].fail=1;
}
int get_fail (int X,int x){
    while (S[n-s[X][x].len-1]!=S[n]) x=s[X][x].fail;
    return x;
}
void ins (int X,int x){
    S[++n]=x;
    int cur=get_fail(X,last);
    if (s[X][cur].son[x]==0){
        int now=new_node(X,s[X][cur].len+2);
        s[X][now].fail=s[X][get_fail(X,s[X][cur].fail)].son[x];
        s[X][cur].son[x]=now;
    }
    last=s[X][cur].son[x];
    s[X][last].cnt++;
}
void count (int X){
    for (int u=p-1;u>=0;u--)
        s[X][s[X][u].fail].cnt+=s[X][u].cnt;
}
typedef long long LL;
LL ans=0;
void dfs (int now1,int now2){
    if (s[0][now1].len>0)
        ans=ans+(LL)s[0][now1].cnt*s[1][now2].cnt;
    for (int u=0;u<26;u++)
        if (s[0][now1].son[u]!=0&&s[1][now2].son[u]!=0)
            dfs(s[0][now1].son[u],s[1][now2].son[u]);
}
int main(){   
    char ch;
    init(0);
    ch=getchar();while (ch<'A'||ch>'Z') ch=getchar();
    while (ch>='A'&&ch<='Z') {
        ins(0,ch-'A');
        ch=getchar();
    }
    count(0);
    init(1);
    ch=getchar();while (ch<'A'||ch>'Z') ch=getchar();
    while (ch>='A'&&ch<='Z') {
        ins(1,ch-'A');
        ch=getchar();
    }
    count(1);
    dfs(0,0);dfs(1,1);
    cout<<ans;
    return 0;
}

end