快乐的jyy"/>

4480: [Jsoi2013]快乐的jyy

给定两个字符串A和B，表示JYY的两个朋友的名字。我们用A(i,j)表示A
字符串中从第i个字母到第j个字母所组成的子串。同样的，我们也可以定义B(x,y)。
JYY发现两个朋友关系的紧密程度，等于同时满足如下条件的四元组(i,j,x,y)
的个数：
1:1<=i<=j<=|A|
2:1<=x<=y<=|B|
3:A(i,j)=B(x,y)
4:A(i,j)是回文串
这里表示字符串A的长度。
JYY希望你帮助他计算出这两个朋友之间关系的紧密程度。

题解

JYY系列终于开发完毕了
回文自动机裸题。。
不会的上网自己查下教程就好了。。
话说我的PAM已经忘得差不多了。。赶紧补了一发

#include<cstdio>
#include<cstring>
using namespace std;
const int N=50005;
struct qq
{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);printf("%lld\n",ans);return 0;
}