2014-2015 ACM-ICPC, Asia Xian Regional Contest GThe Problem to Slow Down You

http://blog.****.net/u013368721/article/details/42100363  回文树

建立两棵回文树，然后count处理一遍就可以了，然后顺着这两棵树的边走下去就好了

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <cstdio>
using namespace std;
const int maxn=;
const int sign_size=;
struct Palind_Tree{
 int next[maxn][sign_size];
 int fail[maxn];
 int cnt[maxn];
 int num[maxn];
 int len[maxn];
 int S[maxn];
 int last;
 int n;
 int p;
 int newnode(int l)
 {
     for(int i=; i<sign_size; i++)next[p][i]=;
     cnt[p]=;
     num[p]=;
     len[p]=l;
     return p++;
 }
 void init()
 {
     p=;
     newnode();
     newnode(-);
     last=;
     n=;
     S[n]=-;
     fail[]=;
 }
 int get_fail(int x)
 {
    while(S[n-len[x]-]!=S[n])x=fail[x];
    return x;
 }
 void add(int c)
 {
     c-='a';
     S[++n]=c;
     int cur=get_fail(last);
     if(next[cur][c]==)
     {
         int now=newnode(len[cur]+);
         fail[now]=next[get_fail( fail[cur] )][c];
         next[cur][c]=now;
         num[now]=num[fail[now]]+;
     }
     last=next[cur][c];
     cnt[last]++;
 }
 void count()
 {
     for(int i=p-; i>=; --i)cnt[fail[i]]+=cnt[i];
 }
}T1,T2;
char S[maxn],S2[maxn];
long long ans=;
void dfs(int u,int v)
{
    for(int i=; i<sign_size; i++)
    {
        int x=T1.next[u][i],y=T2.next[v][i];
        if(x&&y)
        {
            ans+=(long long)T1.cnt[x]*T2.cnt[y];
            dfs(x,y);
        }
    }
}
int main()
{
    int cas;
    scanf("%d",&cas);
    for(int cc=; cc<=cas; cc++)
    {
        scanf("%s%s",S,S2);

        T1.init();
        T2.init();
        int len1=strlen(S);
        int len2=strlen(S2);
        for(int i=; i<len1; i++)
            T1.add(S[i]);
        for(int i=; i<len2; i++)
            T2.add(S2[i]);
        T1.count();
        T2.count();
        ans=;
        dfs(,);
        dfs(,);
        printf("Case #%d: %I64d\n",cc,ans);
    }
    return ;
}