codeforces Gym 100548G - The Problem to Slow Down You 回文树

83 阅读 0 评论 55 点赞

我是靠谱客的博主细心酸奶，最近开发中收集的这篇文章主要介绍codeforces Gym 100548G - The Problem to Slow Down You 回文树，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

直接从两棵树的奇根和偶根dfs就可以了。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<map>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=200100;
const int INF=1e9+10;
char s[maxn],t[maxn];
int ls,lt;
///PalinTree
struct PalinTree
{
int ch[maxn][26],f[maxn];
int tot,n,last;
int s[maxn];
int cnt[maxn],len[maxn];
int L[maxn],R[maxn];
int newnode(int l)
{
MS0(ch[tot]);
cnt[tot]=0;
len[tot]=l;
return tot++;
}
void init()
{
tot=0;
newnode(0);
newnode(-1);
n=last=0;
s[n]=-1;f[0]=1;
len[0]=0;len[1]=-1;
}
int get_fail(int x)
{
while(s[n-len[x]-1]!=s[n]) x=f[x];
return x;
}
void add(int c)
{
c-='a';
s[++n]=c;
last=get_fail(last);
if(!ch[last][c]){
int cur=newnode(len[last]+2);
f[cur]=ch[get_fail(f[last])][c];
ch[last][c]=cur;
R[cur]=n;
L[cur]=n-len[cur]+1;
}
last=ch[last][c];
cnt[last]++;
}
void calc()
{
for(int i=tot-1;i>=0;i--) cnt[f[i]]+=cnt[i];
}
void build(char *str)
{
init();
int ls=strlen(str);
REP(i,0,ls-1) add(str[i]);
}
};PalinTree pt,ps;
ll dfs(int us,int ut)
{
ll res=0;
if(us!=0&&us!=1) res=1LL*ps.cnt[us]*pt.cnt[ut];
REP(c,0,25){
if(ps.ch[us][c]==0||pt.ch[ut][c]==0) continue;
res+=dfs(ps.ch[us][c],pt.ch[ut][c]);
}
return res;
}
ll solve()
{
ps.build(s+1);ps.calc();
pt.build(t+1);pt.calc();
return dfs(0,0)+dfs(1,1);
}
int main()
{
freopen("in.txt","r",stdin);
int T;cin>>T;int casen=1;
while(T--){
printf("Case #%d: ",casen++);
scanf("%s%s",s+1,t+1);
printf("%I64dn",solve());
}
return 0;
}