回文树

回文树可以用来处理一个字符串中所有的回文子串。

一个字符串的回文树由两棵树组成，一个维护所有长度为奇数的回文子串，一个维护所有长度为偶数的回文子串。树上除根节点外的每个节点都表示串中的一个回文子串。

(len:) 节点对应的回文子串长度。

(fail:) 指向该节点所对应的回文子串的最长回文后缀所对应的节点。

(ch:) 转移到该树的另一个节点，转移为向当前回文子串两端加上一个字符。

为方便处理，偶树的根的 (len) 设为 (0)，(fail) 设为奇树的根，奇树的根的 (len) 设为 (-1)，(fail) 设为其本身。

构造时用增量法即可。

(code:)

void init()
{
    len[1]=-1,fail[0]=fail[1]=tot=1;
}
void insert(int i)
{
    int p=las,c=s[i]-'a';
    while(s[i-1-len[p]]!=s[i]) p=fail[p];
    if(ch[p][c])
    {
        las=ch[p][c];
        return;
    }
    int x=fail[p],y=++tot;
    while(s[i-1-len[x]]!=s[i]) x=fail[x];
    fail[y]=ch[x][c],len[y]=len[p]+2,ch[p][c]=las=y,cnt[y]=cnt[fail[y]]+1;
}

建 (fail) 树：

(code:)

for(int i=0;i<=tot;++i)
    if(i!=1)
    	add(fail[i],i);

一个字符串的本质不同回文子串个数即为其回文树除了两个根的节点个数。

字符串中一个位置的回文后缀个数即为该位置对应的节点的 (fail) 链长度。

在维护每个本质不同回文子串的出现次数时，还需在 (fail) 树上用儿子来更新父亲。

(code:)

for(int i=tot;i;--i) cnt[fail[i]]+=cnt[i];

有时还需用到 (trans)，指向长度小于等于其回文子串长度一半的最长回文后缀的节点，建树时维护即可。

(code:)

void insert(int i)
{
    int p=las,c=s[i]-'a';
    while(s[i-1-len[p]]!=s[i]) p=fail[p];
    if(ch[p][c])
    {
        las=ch[p][c];
        return;
    }
    int x=fail[p],y=++tot;
    while(s[i-1-len[x]]!=s[i]) x=fail[x];
    fail[y]=ch[x][c],len[y]=len[p]+2,ch[p][c]=las=y;
    if(len[y]<=2) trans[y]=fail[y];
    else
    {
        int q=trans[p];
        while(s[i-1-len[q]]!=s[i]||(len[q]+2)*2>len[y]) q=fail[q];
        trans[y]=ch[q][c];
    }
}