题意：给你两个字符串，问你有多少对公共回文串。
思路：先对a字符串建回文树。然后再把b字符串加进去就好了。
#include<cstdio> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<stack> #include<cstring> #include<queue> #include<set> #include<string> #include<map> #include <time.h> #define PI acos(-1) using namespace std; typedef long long ll; typedef double db; const int maxn = 400005+1000; const int sigma=26; const ll mod = 1000000007; const int INF = 0x3f3f3f; const db eps = 1e-9; struct ptree{ char s[maxn]; int next[maxn][sigma], fail[maxn], len[maxn]; ll cntt[maxn], cnt[maxn]; int last, n, p; ll res; inline int newnode(int l) { memset(next[p], 0, sizeof(next[p])); cnt[p]=0; cntt[p]=0; len[p]=l; return p++; } inline void init() { n=0, p=0, last=0; newnode(0), newnode(-1); s[n]=-1; fail[0]=1; } void initt() { n=0, last=0; s[0]=-1; fail[0]=1; } inline int FL(int x) { while(s[n-len[x]-1]!=s[n]) x=fail[x]; return x; } void add(char c) { c-='a'; s[++n]=c; int cur=FL(last); if (!next[cur][c]) { int now=newnode(len[cur]+2); fail[now]=next[FL(fail[cur])][c]; next[cur][c]=now; } last=next[cur][c]; ++cnt[last]; } inline ll countt() { for (int i=p-1; ~i; --i) { cnt[fail[i]]+=cnt[i]; } } void add1(char c) { c-='a'; s[++n]=c; int cur=FL(last); if (!next[cur][c]) { int now=newnode(len[cur]+2); fail[now]=next[FL(fail[cur])][c]; next[cur][c]=now; } last=next[cur][c]; ++cntt[last]; } inline ll countt1() { for (int i=p-1; ~i; --i) { cntt[fail[i]]+=cntt[i]; } } ll cal() { //cnt是a字符串的个数，cntt是a相同的回文串的个数 ll pk=0; for (int i=2; i<p; i++) { pk += cnt[i]*cntt[i]; } return pk; } }p; char a[maxn], b[maxn]; void solve(){ scanf("%s", a); int len=strlen(a); scanf("%s", b); int lenn=strlen(b); p.init(); //对a建回文树 for (int i=0; i<len; i++) { p.add(a[i]); } p.countt(); p.initt(); //再次初始化 for (int i=0; i<lenn; i++) { p.add1(b[i]); } p.countt1(); ll ans=p.cal(); static int pa=1; printf("Case #%d: %lld ", pa++, ans); } int main() { int t = 1; //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); scanf("%d", &t); while(t--) { solve(); } return 0; }