#include <iostream>

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 210005 ;

const int N = 26 ;

struct Palindromic_Tree {

int next[MAXN][N] ;//next指针，next指针和字典树类似，指向的串为当前串两端加上同一个字符构成

int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点

long long cnt[MAXN] ;

int num[MAXN] ;

int len[MAXN] ;//len[i]表示节点i表示的回文串的长度

int S[MAXN] ;//存放添加的字符

int last ;//指向上一个字符所在的节点，方便下一次add

int n ;//字符数组指针

int p ;//节点指针

int newnode ( int l ) {//新建节点

for ( int i = 0 ; i < N ; ++ 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 ) {//和KMP一样，失配后找一个尽量最长的

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] ;//和AC自动机一样建立fail指针，以便失配后跳转

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] ;

//父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！

}

void print()

{

//    for(int i=0;i<=p;i++)

//        {

//            printf("%c ",S[i]+'a');

//        }

//        printf("\n");

    for(int i=2;i<p;i++)

        {

            printf("%d ",cnt[i]);

        }

        printf("\n");

}

} ;

Palindromic_Tree a1,b1;

long long ans;

char a[201312],b[223123];

void dfs(int x,int y)

{

    for(int i=0;i<N;i++)

    {

        int x1 =a1.next[x][i];

        int y1 =b1.next[y][i];

        if(x1&&y1)

        {

            ans+=(long long)(a1.cnt[x1]*b1.cnt[y1]);

            cout<<x1<<" "<<y1<<" "<<a1.cnt[x1]<<" "<<b1.cnt[y1]<<endl;

            dfs(x1,y1);

        }

    }

}

int main()

{

    int T;

    cin>>T;

    int yy =0;

    while(T--)

    {

        scanf("%s%s",a,b);

        yy++;

        printf("Case #%d: ",yy);

        int len1 =strlen(a);

        int len2 =strlen(b);

         a1.init();

         b1.init();

        for(int i=0;i<len1;i++)

        {

            a1.add(a[i]);

        }

        for(int i=0;i<len2;i++)

        {

            b1.add(b[i]);

        }

        a1.count();

        b1.count();

        a1.print();

        cout<<endl;

        b1.print();

        ans =0 ;

        dfs(0,0);

//        cout<<endl;

//        cout<<endl;

        dfs(1,1);

        cout<<ans<<endl;

    }

    return 0;

}

介绍

简介

回文树（回文自动机），是解决一类回文串问题的强大数据结构，比Manacher$Manacher$扩展了很多功能。 
这个数据结构比较新，由来自战斗民族的神犇MikhailRubinchik在2014年的Petrozavodsk夏令营提出。 
这个数据结构代码量其实超级少。

必备技能

Manacher$Manacher$ 
最好会至少一种自动机

分析

回文树严格来讲是由两棵树构成的森林，再加上一堆后缀链（失配链）。其中一棵树代表长度为奇数的回文串，另一棵树代表长度为偶数的回文串。树上每个节点都代表一种与其它节点不同的回文串，所以每个点上都有诸如长度len$len$和出现次数cnt$cnt$之类的权值。 
后缀链fail$fail$连向代表以这个点代表的回文串的最长回文后缀的点（有点长，自己断句）。 
初始时，偶数树的根节点代表一个空串，长度为0$0$，后缀链连向奇数树的根节点。奇数树的根节点则比较神，代表一个被吞掉一个字符的串（是不是很鬼畜？？？），长度为−1$-1$（后面会讲为什么要这样），后缀链连向它自己。 
插入操作过程中，我们需要记录当前插入的串的最长回文后缀suf$suf$。设原串为s$s$，当我们要加入第i$i$个字符时，我们就从suf$suf$这个点开始，往后缀链一直跳，直到到达一个点x$x$使得s[i−1−len[x]]=s[i]$s[i-1-len[x]]=s[i]$，也就是该点代表的回文后缀两边字符相等，可以变成一个新的回文串（注意：当我们跳到奇数树根时，s[i−1−len[x]]=s[i−1−(−1)]=s[i]$s[i-1-len[x]]=s[i-1-(-1)]=s[i]$，这样我们加入本质为单个字符的回文串了）。 
我们找到x$x$点后，先判断x$x$是否存在两边字符为s[i]$s[i]$的儿子节点，如果有，就将儿子节点的cnt$cnt$加一。否则新建节点，cnt$cnt$为1$1$。那么新建点的后缀链怎么弄呢？我们可以对fail[x]$fail[x]$做同样的过程（还是一直往fail$fail$跳，找合法节点），那么该点的s[i]$s[i]$儿子就是我们要找的fail$fail$（当然存在找不到的情况，我们就将其fail$fail$设为空串即偶数树根，这个在实现时，我们可以将每个点不存在的儿子初始为偶数树根，这样就不用特判了）。

由于blog主特别懒，这里就不配图了，大家结合代码理解理解吧。

建完树，我们要重算一次每个回文串出现次数。过程很简单，就是倒序枚举节点，假设枚举到x$x$，我们给cnt[fail[x]]$cnt[fail[x]]$加上cnt[x]$cnt[x]$即可。 
然后剩下的就是结合题目乱搞了。