bzoj 4480: [Jsoi2013]快乐的jyy

快乐的jyy"/>

bzoj 4480: [Jsoi2013]快乐的jyy

题意：

给两个串，求两个相同的回文串，在两个串中出现过，位置不同算不同。求方案数。

题解：

回文自动机裸题，当然bzoj3676更裸，记得有一篇博客写的很好，关于回文自动机的，但是忘了是哪篇，好像从hzwer中连接过去的。
code：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#define LL long long
using namespace std;
struct PAM{
    int a[27],fail,cnt,num,len;
}pam[2][50010];int tail,num,tot;
LL ans=0;
int S[50010];
char s[2][50010];
void add(int len,int op){pam[op][++tot].len=len;}
void init(int op)
{
    num=0;tot=-1;tail=0;
    add(0,op);add(-1,op);
    S[num]=-1;pam[op][0].fail=1;
}
int getfail(int x,int op)
{
    while(S[num-pam[op][x].len-1]!=S[num]) x=pam[op][x].fail;
    return x;
}
void addpam(int c,int op)
{
    S[++num]=c;
    int cur=getfail(tail,op);
    if(!pam[op][cur].a[c])
    {
        add(pam[op][cur].len+2,op);
        pam[op][tot].fail=pam[op][getfail(pam[op][cur].fail,op)].a[c];
        pam[op][cur].a[c]=tot;
        pam[op][tot].num=pam[op][pam[op][tot].fail].num+1;
    }
    tail=pam[op][cur].a[c];
    pam[op][tail].cnt++;
}
void count(int op){for(int i=tot;i>=0;i--) pam[op][pam[op][i].fail].cnt+=pam[op][i].cnt;}
void dfs(int x,int y)
{
    if(x!=0&&x!=1&&y!=0&&y!=1) ans+=(LL)pam[0][x].cnt*(LL)pam[1][y].cnt;
    for(int i=0;i<26;i++)
        if(pam[0][x].a[i]!=0&&pam[1][y].a[i]!=0)
            dfs(pam[0][x].a[i],pam[1][y].a[i]);
}
int main()
{
    scanf("%s %s",s[0]+1,s[1]+1);
    int n0=strlen(s[0]+1),n1=strlen(s[1]+1);
    init(0);for(int i=1;i<=n0;i++) addpam(s[0][i]-'A',0);count(0);
    init(1);for(int i=1;i<=n1;i++) addpam(s[1][i]-'A',1);count(1);
    dfs(0,0);dfs(1,1);
    printf("%lld",ans);
}