UVAlive 7041 The Problem to Slow Down You（回文树）

题目链接：

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5053

先把第一个串插入回文树中，然后把s数组清空插入第二个串，统计两个cnt数组，答案是二者相乘的结果

#include <iostream>

#include <stdlib.h>

#include <algorithm>

#include <stdio.h>

#include <math.h>

#include <string.h>

using namespace std;

typedef long long int LL;

const int maxn=2e5+5;

char str1[maxn];

char str2[maxn];

int n;

LL ans;

struct Tree

{

	const static int maxn=4e5+5;

    int next[maxn][26];

    int fail[maxn];

    LL  cnt[maxn];

    LL  cnt2[maxn];

    int len[maxn];

    int s[maxn];

    int last,p,n;

    int new_node(int x)

    {

        memset(next[p],0,sizeof(next[p]));

        cnt[p]=0;

        cnt2[p]=0;

        len[p]=x;

        return p++;

    }

       void init()

    {

        //memset(cnt,0,sizeof(cnt));

        //memset(cnt2,0,sizeof(cnt2));

        p=0;

        new_node(0);

        new_node(-1);

        last=0;

        n=0;

        s[0]=-1;

        fail[0]=1;

    }

    void init2()

    {

        last=0;

        s[0]=-1;

		fail[0]=1;

        n=0;

    }

    int get_fail(int x)

    {

        while(s[n-len[x]-1]!=s[n])

            x=fail[x];

        return x;

    }

    void add(int x)

    {

        x-='a';

        s[++n]=x;

        int cur=get_fail(last);

        if(!(last=next[cur][x]))

        {

            int now=new_node(len[cur]+2);

            fail[now]=next[get_fail(fail[cur])][x];

            next[cur][x]=now;

            last=now;

        }

        cnt[last]++;

    }

    void add2(int x)

    {

        x-='a';

        s[++n]=x;

        int cur=get_fail(last);

        if(!(last=next[cur][x]))

        {

            int now=new_node(len[cur]+2);

            fail[now]=next[get_fail(fail[cur])][x];

            next[cur][x]=now;

            last=now;

        }

        cnt2[last]++;

    }

    void count()

    {

        for(int i=p-1;i>=0;i--)

            cnt[fail[i]]+=cnt[i];

    }

    void count2()

    {

        for(int i=p-1;i>=0;i--)

            cnt2[fail[i]]+=cnt2[i];

    }

    void fun()

    {

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

        {

            ans+=cnt[i]*cnt2[i];

        }

    }

}tree;

int main()

{

    scanf("%d",&n);

    for(int j=1;j<=n;j++)

    {

        scanf("%s%s",str1,str2);

        tree.init();

        int len=strlen(str1);

        int len1=strlen(str2);

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

        {

            tree.add(str1[i]);

        }

        tree.count();

        tree.init2();

        ans=0;

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

        {

            tree.add2(str2[i]);

        }

        tree.count2();

        tree.fun();

        printf("Case #%d: %lld\n",j,ans);

    }

    return 0;

}