本文移植自个人的原博客（原文）

概念

回文树能够以$O(n)$的时间求出字符串中本质不同的回文串个数（最多为$n$个，证明考虑每次插入一个新的后缀，如果形成的新的最长回文串不是整个串，则一定在前面插入时出现过）和其长度与出现次数。

回文树中每个节点表示的是一个回文串，第一种边以$son[x][ch]$存储，指向的是$x$所代表的回文串前后各插入一个$ch$所形成的字符串，第二种边为后缀链接边(suffix link)，指向的是$x$所代表的回文串其最长的回文子串（与$x$不相等），以$f[x]$表示。初始化为一个长度为$0$的节点（标号应为$0$）和长度为$−1$的节点，其中前者的$f$指向后者，具体原因见下文代码注释。

构造

从左到右一个字符一个字符地处理，始终维护着当前已处理前缀的最长后缀回文串（初始时为空串）。每次扫描一个新的字符$x$时，我们就沿着最长后缀回文串的$f$找到一个回文串$A$，它的两边可以同时添加字符$x$，得到一个合法的后缀回文串。$xAx$是新节点的唯一候选，为了得到它的$f$，我们需要继续沿着链接走，直到找到另一个回文串$B$，它的两边添加字符$x$可以得到$xAx$的合法后缀回文串，于是添加一条从$xAx$到$xBx$的$f$边（当然，如果这条边已经存在就不用了）。

实现如下：

struct PalindromesTree{
    int tot,last,l[N],son[N][26],c[N],f[N];

    int newnode(int x){
        l[++tot]=x;return tot;
    }

    void init(){
        tot=-1;last=0;
        f[newnode(0)]=1;f[newnode(-1)]=0;
    }

    int get(int x,int n){
        while(s[n]!=s[n-l[x]-1])x=f[x];
        return x;
        //沿着最长后缀回文串的$f$找到一个回文串A，它的两边可以同时添加字符x
        //如果找不到的话，那么会先遍历到长度为$0$的节点，判断能否形成s[n-1],s[n]这样一个回文串，否则来到长度为$-1$的节点，一定能形成一个s[n]单个字符的回文串。
    }

    int add(int x,int i){
        int y=get(last,i);//last即为维护的最长后缀回文串
        if(!son[y][x]){
            int now=newnode(l[y]+2);//now代表的回文串为y代表的回文串在两边加入xx形成。
            f[now]=son[get(f[y],i)][x];//更新f，理由get函数注释
            son[y][x]=now;
        }
        c[last=son[y][x]]++;//表示出现次数，最后要更新c[f[x]]+=c[x]，因为如果产生了一个新的回文串的话，那么其所有子串是没有计算c的变化的。
    }

    ll solve(){
        for(int i=1;i<=n;++i)add(s[i]-'a',i);
        for(int i=tot;i>=1;--i)c[f[i]]+=c[i];
        return ret;
    }
}T;

相关题目

APIO2014 Palindromes

题目链接

UOJ 103

题解

虚树模板题。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5+2;

char s[N];
int n;

struct PalindromesTree{
    int tot,last,l[N],son[N][26],c[N],f[N];

    int newnode(int x){
        l[++tot]=x;return tot;
    }

    void init(){
        tot=-1;last=0;
        f[newnode(0)]=1;f[newnode(-1)]=0;
    }

    int get(int x,int n){
        while(s[n]!=s[n-l[x]-1])x=f[x];
        return x;
    }

    int add(int x,int i){
        int y=get(last,i);
        if(!son[y][x]){
            int now=newnode(l[y]+2),ne=get(f[y],i);
            f[now]=son[ne][x];
            son[y][x]=now;
        }
        c[last=son[y][x]]++;
    }

    ll solve(){
        for(int i=1;i<=n;++i)add(s[i]-'a',i);
        for(int i=tot;i>=1;--i)c[f[i]]+=c[i];
        ll ret=0;
        for(int i=1;i<=tot;++i)ret=max(ret,(ll)l[i]*c[i]);
        return ret;
    }
}T;

int main(){
    scanf("%s",s+1);
    T.init();
    n=strlen(s+1);
    printf("%lld\n",T.solve());
}

Codechef Palindromeness

题目描述

题解

判断第一个满足条件的后缀回文是否正好为其一半长度，每次递归$f$数组查询显然会TLE，用$hf_x$表示满足小于等于其一半长度的$f_x$记忆化处理即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;

int n;
char s[N];

struct PalindromicTree{
    int tot,last,l[N],son[N][26],hf[N],f[N];
    ll c[N],g[N];
    int newnode(int x){
        l[++tot]=x;
        f[tot]=hf[tot]=c[tot]=0;
        memset(son[tot],0,sizeof(son[tot]));
        return tot;
    }

    void init(){
        last=0;tot=-1;
        if(g[0]!=0||g[1]!=0)while(1);
        newnode(0);f[0]=hf[0]=1;
        newnode(-1);f[1]=0;
    }

    int get(int x,int i){
        while(s[i]!=s[i-l[x]-1])x=f[x];
        return x;
    }

    int add(int x,int i){
        int y=get(last,i);
        if(!son[y][x]){
            int now=newnode(l[y]+2);
            f[now]=son[get(f[y],i)][x];
            hf[now]=son[get(hf[y],i)][x];
            while(l[hf[now]]>l[now]/2)hf[now]=f[hf[now]];
            int fr=hf[now];
            g[now]=1+(l[fr]==l[now]/2)*g[fr];
            son[y][x]=now;
        }
        c[last=son[y][x]]++;
    }

    ll solve(){
        ll ret=0;
        init();
        for(int i=1;i<=n;++i)add(s[i]-'a',i);
        for(int i=tot;i>=1;--i){
            ret+=c[i]*g[i];
            c[f[i]]+=c[i];
        }
        return ret;
    }
}T;

int main(){
//    freopen("c.in","r",stdin);
    int Case;
    scanf("%d",&Case);
    while(Case--){
        scanf("%s",s+1);
        n=strlen(s+1);
        printf("%lld\n",T.solve());
    }
}