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

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

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

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <cstdio>
using namespace std;
const int maxn=300005;
const int sign_size=26;
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=0; i<sign_size; i++)next[p][i]=0;
     cnt[p]=0;
     num[p]=0;
     len[p]=l;
     return p++;
 }
 void init()
 {
     p=0;
     newnode(0);
     newnode(-1);
     last=0;
     n=0;
     S[n]=-1;
     fail[0]=1;
 }
 int get_fail(int x)
 {
    while(S[n-len[x]-1]!=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]==0)
     {
         int now=newnode(len[cur]+2);
         fail[now]=next[get_fail( fail[cur] )][c];
         next[cur][c]=now;
         num[now]=num[fail[now]]+1;
     }
     last=next[cur][c];
     cnt[last]++;
 }
 void count()
 {
     for(int i=p-1; i>=0; --i)cnt[fail[i]]+=cnt[i];
 }
}T1,T2;
char S[maxn],S2[maxn];
long long ans=0;
void dfs(int u,int v)
{
    for(int i=0; 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=1; cc<=cas; cc++)
    {
        scanf("%s%s",S,S2);

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