来源：

优点：

• 代码好写，易于调试
• 由于是树形，功能强大（不过由于回文串的限制，这类题目比较少）

简述

回文树是两棵树，每个节点代表一个回文串。第一棵树的点是长度为偶数的回文串，那第二棵肯定就是奇数的啦。

为了方便，第一棵树的根是一个长度为\(0\)的串，第二棵就是为\(-1\)的串，不要感到奇怪，就是\(-1\)。

可以证明，最多只有\(n\)个结点（\(n\)是串的长度）。这个可以用manacher算法来证明。

如果某结点代表的是串ccabacc，那么它的父亲代表的串就是去掉前后两个字符cabac。

每个点还有一个fail指针，表示这个串的后缀中最长的回文串，比如babab的fail指向bab，bab的指向b。

现来讲讲如何构树，方法的思想和KMP，AC自动机没啥两样，看看代码就立马可以懂了。

模板题

我目前刷了个rank7，相信随着这个算法的普及，我要往下跌了。

update

果不其然，现在已经跌到rank25。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int MAXN = (int) 3e5 + 3;typedef long long i64;template 
        
         void relax(T &a, const T &b) {    if (b > a) a = b;}int n;char str[MAXN];struct Node {    Node* s[26];    Node* fail;    int len;    int cnt;};Node mem[MAXN];Node* curMem = mem;Node* getFail(Node* x, int i) {    while (i == x->len || str[i] != str[i - x->len - 1])        x = x->fail;    return x;}int main() {#ifndef ONLINE_JUDGE    freopen("input.txt", "r", stdin);#endif    scanf("%s", str);    n = strlen(str);    Node* root0 = curMem ++;    Node* root1 = curMem ++;    root0->fail = root1;    root1->len = -1;    Node* cur = root1;    for (int i = 0; i < n; i ++) {        int p = str[i] - 'a';        cur = getFail(cur, i);        if (! cur->s[p]) {            Node* x = curMem ++;            cur->s[p] = x;            x->len = cur->len + 2;            if (cur == root1)                 x->fail = root0;            else                x->fail = getFail(cur->fail, i)->s[p];        }        cur = cur->s[p];        cur->cnt ++;    }    i64 ans = 0;    for (Node* pt = curMem - 1; pt >= mem; pt --) {        if (pt == root0 || pt == root1) continue;        pt->fail->cnt += pt->cnt;        relax(ans, (i64) pt->len * pt->cnt);    }    cout << ans << endl;    return 0;}