P5685 [JSOI2013]快乐的 JYY 题解
violetctl39
·
·
题解
题目大意：给你两个字符串，求它们的公共回文子串对数。
大部分人的做法是对 A 建 PAM ，然后把 B 放在上面匹配；或是建两个 PAM ，然后一起 dfs 匹配。
其实可以直接上 广义PAM （应该可以这么叫吧），把两个字符串建到一个 广义PAM ，然后 dfs 所有节点统计答案。
能建 广义PAM 的理由：
设 $f[x][0]$ 是 $A$ 串在 $x$ 节点上的回文子串数，$f[x][1]$ 是 $B$ 串在 $x$ 节点上的回文子串数。
那么答案即为 $\large \sum\limits_{i=2}^{cnt}f[x][0]\times f[x][1]$ 。（ $cnt$ 是节点数，0和1是根）
代码：
```cpp
#include<bits/stdc++.h>
#define pc(x) putchar(x)
#define ll long long
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){f=ch=='-'?-1:f;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
void write(ll x)
{
if(x<0){x=-x;putchar('-');}
if(x>9)write(x/10);
putchar(x%10+48);
}
int n,m,f[100005][2];ll ans;
char s[50005];
struct G_PAM
{
int ch[26],fa,len;
}tr[100005];
int lst,cnt=1;
void init()
{
s[0]=-1;tr[1].len=-1;
tr[0].fa=tr[1].fa=1;
lst=0;
}
void insert(int k,int c,int id)
{
int p=lst;
while(s[k-tr[p].len-1]!=c+'A')p=tr[p].fa;
if(!tr[p].ch[c])
{
int q=lst=++cnt,v=tr[p].fa;
while(s[k-tr[v].len-1]!=c+'A')v=tr[v].fa;
tr[q].fa=tr[v].ch[c];
tr[tr[p].ch[c]=q].len=tr[p].len+2;
}else lst=tr[p].ch[c];
f[lst][id]++;
}
vector<int>e[600005];
void dfs(int x)
{
for(int i=0;i<(int)e[x].size();++i)
{
int y=e[x][i];dfs(e[x][i]);
f[x][0]+=f[y][0];f[x][1]+=f[y][1];
}
if(x==1||x==0)return;
ans+=1ll*f[x][0]*f[x][1];
}
int main()
{
scanf("%s",s+1);n=strlen(s+1);init();
for(int i=1;i<=n;++i)insert(i,s[i]-'A',0);
scanf("%s",s+1);n=strlen(s+1);init();
for(int i=1;i<=n;++i)insert(i,s[i]-'A',1);
for(int i=2;i<=cnt;++i)e[tr[i].fa].push_back(i);
e[1].push_back(0);dfs(1);write(ans),pc('\n');
return 0;
}
```