题目描述

给我们两个只有大写字母的字符串A和B,求他们的亲密程度。
亲密程度等于满足如下条件的四元组(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) 是回文串

1<=|A|,|B|<=5e4

样例

输入

PUPPY
PUPPUP

输出

17

分析

将两个字符串插入到一个PAM上,在PAM上每个节点维护两个cnt,节点u的cnt1表示第一个字符串中子串u的出现次数,cnt2表示第二个字符串中子串u的出现次数,答案就是将每个节点的cnt1和cnt2相乘再相加.

PAM

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int tr[N][26],idx,tot,last;
int fail[N];
int len[N],cnt[2][N];
char s[N];
int node(int x){
    len[idx++]=x;
    return idx-1;
}
void init(){
    node(0);
    node(-1);
    fail[0]=1,fail[1]=0;
}
int get_fail(int x){
    while(s[tot-len[x]-1]!=s[tot]){
        x=fail[x];
    }
    return x;
}
void insert(int f,char c){
    tot++;
    int now=get_fail(last);
    if(!tr[now][c-'A']){
        int x=node(len[now]+2);
        fail[x]=tr[get_fail(fail[now])][c-'A'];
        tr[now][c-'A']=x;
    }
    last=tr[now][c-'A'];
    cnt[f][last]++;
}
int main(){
    init(); 
    cin>>s+1;
    int l=strlen(s+1);
    for(int i=1;i<=l;i++)insert(0,s[i]);
    cin>>s+1;
    tot=0;
    l=strlen(s+1);
    for(int i=1;i<=l;i++)insert(1,s[i]);
    for(int i=idx-1;i>1;i--){
        cnt[0][fail[i]]+=cnt[0][i];
        cnt[1][fail[i]]+=cnt[1][i];
    }
    long long ans=0;
    for(int i=2;i<idx;i++)ans+=(long long)cnt[0][i]*cnt[1][i];
    cout<<ans;
    return 0;
}