BZOJ4480：快乐的jyy（回文自动机）

自动机）"/>

BZOJ4480：快乐的jyy（回文自动机）

题面
题意：给出两个串，问所有回文串在两个串出现次数之积之和。

应该是回文自动机果题
插完一个串后重置last，再插入另一个串
每个状态对于两个串分别统计Right集的大小
就可以统计答案了

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>using namespace std;
#define mmst(a, b) memset(a, b, sizeof(a))
#define mmcp(a, b) memcpy(a, b, sizeof(b))typedef long long LL;const int N=200200;int n;
int son[N][26],pre[N],len[N],r[N][2],last,cnt;
char s[N];
LL ans;void Insert(int pos,int ops)
{int x=last,ch=s[pos]-'A';while(s[pos-len[x]-1]!=s[pos])x=pre[x];if (!son[x][ch]){len[++cnt]=len[x]+2;int y=pre[x];while(s[pos-len[y]-1]!=s[pos])y=pre[y];pre[cnt]=son[y][ch];son[x][ch]=cnt;}x=son[x][ch];r[x][ops]++;last=x;
}int main()
{pre[1]=pre[0]=cnt=1;len[1]=-1;scanf("%s",s+1);n=strlen(s+1);for(int i=1;i<=n;i++)Insert(i,0);last=0;scanf("%s",s+1);n=strlen(s+1);for(int i=1;i<=n;i++)Insert(i,1);for(int i=cnt;i>=2;i--)if(pre[i]>1)r[pre[i]][0]+=r[i][0],r[pre[i]][1]+=r[i][1];for(int i=2;i<=cnt;i++)ans+=(LL)r[i][0]*r[i][1];cout<<ans<<endl;return 0;
}