题目链接：https://vjudge.net/problem/UVALive-7041

题意：求两个串的公共回文串的个数。

解法：回文树。回文树学习资料：http://blog.csdn.net/u013368721/article/details/42100363

然后这题就成为了裸题。从0和1两个根节点DFS下去，如果两个相同的节点同时存在就统计答案。


#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 200010;
const int maxs = 26;
struct Palindromic_Tree{
    int next[maxn][maxs];
    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<maxs; 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]){
            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];
    }
};

Palindromic_Tree T1, T2;
char s1[maxn], s2[maxn];
int n1, n2;
LL ans;

void dfs(int u, int v){
    for(int i=0; i<maxs; i++){
        int x = T1.next[u][i], y = T2.next[v][i];
        if(x && y){
            ans += (LL)T1.cnt[x]*T2.cnt[y];
            dfs(x, y);
        }
    }
}

int main()
{
    int T, ks = 0;
    scanf("%d", &T);
    while(T--)
    {
        printf("Case #%d: ", ++ks);
        ans = 0;
        T1.init();
        T2.init();
        scanf("%s%s", s1, s2);
        n1 = strlen(s1);
        n2 = strlen(s2);
        for(int i=0; i<n1; i++) T1.add(s1[i]);
        for(int i=0; i<n2; i++) T2.add(s2[i]);
        T1.count();
        T2.count();
        dfs(0, 0);
        dfs(1, 1);
        printf("%lld\n", ans);
    }
    return 0;
}