題目鏈接：
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5053
先把第一個串插入回文樹中，然后把s數組清空插入第二個串，統計兩個cnt數組，答案是二者相乘的結果
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <string.h>using namespace std;
typedef long long int LL;
const int maxn=2e5+5;
char str1[maxn];
char str2[maxn];
int n;
LL ans;
struct Tree
{const static int maxn=4e5+5;int next[maxn][26];int fail[maxn];LL cnt[maxn];LL cnt2[maxn];int len[maxn];int s[maxn];int last,p,n;int new_node(int x){memset(next[p],0,sizeof(next[p]));cnt[p]=0;cnt2[p]=0;len[p]=x;return p++;}void init(){//memset(cnt,0,sizeof(cnt));//memset(cnt2,0,sizeof(cnt2));p=0;new_node(0);new_node(-1);last=0;n=0;s[0]=-1;fail[0]=1;}void init2(){last=0;s[0]=-1;fail[0]=1;n=0;}int get_fail(int x){while(s[n-len[x]-1]!=s[n])x=fail[x];return x;}void add(int x){x-='a';s[++n]=x;int cur=get_fail(last);if(!(last=next[cur][x])){int now=new_node(len[cur]+2);fail[now]=next[get_fail(fail[cur])][x];next[cur][x]=now;last=now;}cnt[last]++;}void add2(int x){x-='a';s[++n]=x;int cur=get_fail(last);if(!(last=next[cur][x])){int now=new_node(len[cur]+2);fail[now]=next[get_fail(fail[cur])][x];next[cur][x]=now;last=now;}cnt2[last]++;}void count(){for(int i=p-1;i>=0;i--)cnt[fail[i]]+=cnt[i];}void count2(){for(int i=p-1;i>=0;i--)cnt2[fail[i]]+=cnt2[i];}void fun(){for(int i=2;i<=p-1;i++){ans+=cnt[i]*cnt2[i];}}}tree;
int main()
{scanf("%d",&n);for(int j=1;j<=n;j++){scanf("%s%s",str1,str2);tree.init();int len=strlen(str1);int len1=strlen(str2);for(int i=0;i<len;i++){tree.add(str1[i]);}tree.count();tree.init2();ans=0;for(int i=0;i<len1;i++){tree.add2(str2[i]);}tree.count2();tree.fun();printf("Case #%d: %lld\n",j,ans);}return 0;
}
轉載于:https://www.cnblogs.com/dacc123/p/8228629.html
總結
以上是生活随笔為你收集整理的UVAlive 7041 The Problem to Slow Down You（回文树）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
