2019 ACM/ICPC南京网络赛 G题Colorful String（回文树）

题目链接： 传送门

题意：

一个字符串的价值为其字符串中出现字符的种类个数，现在给你一个字符串S，求S中所有回文串的价值。

思路：

我们可以构建一颗回文树，并且在构建过程记录每个回文串节点中字符种类个数。最后遍历所有不同的回文串节点统计和即可。
代码：

#include <bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int N=3e5+10;
struct PA_tree
{
    static const int branch=26;
    static const int MAXN=3e5+10;
    struct Node //每个节点代表一个回文串
    {
        ll len,cnt;//回文串的长度,回文串出现次数
        int next[branch],fail;
        int book[branch],dif;
        //next[c]:该节点左右增加字符c的回文串节点位置,默认为0
        //fail :该节点非本身的最长回文后缀节点
    } node[MAXN];
    int ls,top=0;//长度,此时使用的节点个数
    char *s;//字符首指针,下标从1开始
    int initnode(int id)//需要手动初始化fail和len
    {
        node[id].cnt=0;
        mset(node[id].next,0);
        mset(node[id].book,0);
        return id;
    }
    int getfail(int last,int i)
    {
        while(s[i-node[last].len-1]!=s[i]) last=node[last].fail;
        return last;
    }
    void init(char *s,int ls)
    {
        this->s=s;
        this->ls=ls;
        top=0;
        initnode(top++);
        initnode(top++);
        node[0].fail=1;
        node[1].fail=0x3f3f3f3f;
        node[0].len=0,node[1].len=-1;
        node[0].dif=node[1].dif=0;
        s[0]=-1;
    }
    int gv(char c)
    {
        return c-'a';
    }
    void bulid_tree()
    {
        //目标,构建fail指针并生成回文树
        int last=0;
        for(int i=1; i<=ls; ++i)
        {

            int c=gv(s[i]);
            int cur=getfail(last,i);
            int now=node[cur].next[c];
            if(!now)
            {
                now=initnode(top++);//新建一个新的节点作为儿子
                node[now].len=node[cur].len+2;
                node[now].fail=node[getfail(node[cur].fail,i)].next[c];
                node[cur].next[c]=now;
                if(node[cur].book[c]==0) node[now].dif=node[cur].dif+1;
                else node[now].dif=node[cur].dif;
                for(int j=0;j<branch;++j)
                    node[now].book[j]=node[cur].book[j];
                node[now].book[c]=1;

            }
            node[now].cnt++;
            last=now;
        }
    }
    void calc_count()
    {
        //基于fail的节点标号一定比自身小,所以我们倒着累加
        for(int i=top-1; i; --i)
            node[node[i].fail].cnt+=node[i].cnt;
    }
    ll getans()
    {
        ll ans=0;
        for(int i=2;i<top;++i)
            ans+=node[i].cnt*node[i].dif;
        return ans;
    }

};
char s[N];
PA_tree solve;
int main()
{
    scanf("%s",s+1);
    int ls=strlen(s+1);
    solve.init(s,ls);
    solve.bulid_tree();
    solve.calc_count();
    printf("%lld\n",solve.getans());
    return 0;
}