【问题描述】
给定两个字符串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希望你帮助他计算出这两个朋友之间关系的紧密程度。
建两个串的回文树，算出每个本质不同的回文串在两个串中出现次数，乘起来相加。
#include<bits/stdc++.h>
typedef long long i64;
const int N=1e5+;
char s1[],s2[];
int nx[N][],fa[N],l[N],t[N][],pv=,ptr=;
int gf(int w,char*s,int i){
while(s[i]!=s[i--l[w]])w=fa[w];
return w;
}
void ins(char*s,int x){
int c=s[x]-'A',p=gf(pv,s,x);
if(!nx[p][c]){
int np=nx[p][c]=++ptr;
l[np]=l[p]+;
fa[np]=p==?:gf(fa[p],s,x)[nx][c];
}
pv=nx[p][c];
++t[pv][s==s2];
}
int main(){
l[]=-;
fa[]=fa[]=;
scanf("%s%s",s1+,s2+);
s1[]=s2[]=-;
for(int i=;s1[i];++i)ins(s1,i);
pv=;
for(int i=;s2[i];++i)ins(s2,i);
i64 ans=;
for(int w=ptr;w>;--w){
int f=fa[w];
for(int d=;d<;++d)t[f][d]+=t[w][d];
ans+=i64(t[w][])*t[w][];
}
printf("%llu\n",ans);
return ;
}