咱們可以先從字面意思來理解什么是回文樹，回文樹 (回文自動機) 實際上是奇偶兩棵樹，每一個節(jié)點代表一個本質(zhì)不同的回文子串（一棵樹上的串長度全部是奇數(shù)，另一棵全部是偶數(shù)），原串中每一個本質(zhì)不同的回文子串都在樹上出現(xiàn)一次且僅一次。

一個節(jié)點的 fail 指針指向它的最長回文后綴（不包括自身，所有空 fail 均連向 1）。歸納容易證明，當(dāng)在原串末尾新增一個字符時，回文樹上至多會新增一個節(jié)點，這也證明了一個串本質(zhì)不同的回文子串個數(shù)不會超過 n。

建樹時采用增量構(gòu)造法，當(dāng)考慮新字符 s [i] 時，先找到以 s [i-1] 為結(jié)尾的節(jié)點 p，并不斷跳 fail。若代表新增回文子串的節(jié)點已存在則直接結(jié)束，否則通過 fail [p] 不斷跳 fail 找到新節(jié)點的 fail。

0,1 號節(jié)點均不代表串，常數(shù)大于 manacher。初始化 fail [0]=fail [1]=1,len [1]=-1,tot=1,last=0。

概述

回文自動機（簡稱PAM，又稱回文樹，Palindromic Tree）是一種用于處理回文串的結(jié)構(gòu)，在其結(jié)構(gòu)內(nèi)可以找到原串中的所有回文子串，顧名思義，回文樹是一個用來解決回文串相關(guān)問題的數(shù)據(jù)結(jié)構(gòu)。

結(jié)構(gòu)

就像線段樹、平衡樹等其它樹結(jié)構(gòu)一樣，回文樹由若干個節(jié)點組成，每個節(jié)點代表一個回文串(palindrome)。

如圖為串a(chǎn)bba的PAM示意圖，其中，實線表示回文串的擴展轉(zhuǎn)移邊，虛線表示后綴鏈接。

節(jié)點信息

每個節(jié)點對應(yīng)一個唯一的回文子串。

（1）回文串出現(xiàn)的次數(shù)cnt(u)

（2）回文串的長度len(u)

（3）可以不保存具體的字符串信息

為了方便，我們規(guī)定，偶回文樹樹根len(rt0)=0，奇回文樹樹根len(rt1)=?1。

轉(zhuǎn)移邊

轉(zhuǎn)移邊u→v對節(jié)點的意義是，將u對應(yīng)的回文串左右兩邊加上同一個字符c得到節(jié)點v對應(yīng)的回文串。

失配邊

指向該節(jié)點對應(yīng)子串的最長回文后綴

為了方便我們規(guī)定偶回文樹樹根rt0指向奇回文數(shù)根rt1

節(jié)點信息轉(zhuǎn)移

記對應(yīng)回文串出現(xiàn)的次數(shù)cnt(u),則 $$cnt(u)=\sum _{v=son(u)} {cnt(v)}$$

記對應(yīng)回文串的長度len(u)，若節(jié)點v是由節(jié)點u轉(zhuǎn)移而來的，則有l(wèi)en(v)=len(u)+2

構(gòu)造

和后綴自動機類似，用增量法構(gòu)造，每次在母串后插入一個字符，更新PAM的復(fù)雜度是O(1)的，因此構(gòu)造自動機是O(n)的。

我們記錄上一次插入節(jié)點的位置last，對于新插入的字符c，我們檢查之前的最長回文后綴的前一個字母是否和c相同，如果相同，那么就創(chuàng)建一個新的節(jié)點，否則我們沿著適配邊找最長回文后綴的最長回文后綴（稍微有點繞口） 如當(dāng)前的母串是 $$caba$$ 現(xiàn)在我要插入新的字符 b。

那么我先看到最長回文后綴aba的前一個字母是c，和新插入的字符a不同（因此cabab不能組成回文子串），因此我沿著失配邊找到aba的最長回文后綴a，由于前一個字符b與新插入的字符相同，能組成新回文子串a(chǎn)ba，因此新建節(jié)點。

稍微注意的是s[0]賦值為一個特殊字符。

模板如下：

#include <bits/stdc++.h>#define rep(i, a, b) for (int i=a; i<=b; i++)#define drep(i, a, b) for (int i=a; i>=b; i--)#define inf 1e9using namespace std;typedef long long ll;const int maxn=300010;char s[maxn];int n;struct Ptree {
    int last;
    struct Node {
        int cnt, lenn, fail, son[27];
        Node(int lenn, int fail):lenn(lenn), fail(fail), cnt(0){
            memset(son, 0, sizeof(son));
        };
    };
    vector<Node> st;
    inline int newnode(int lenn, int fail=0) {
        st.emplace_back(lenn, fail);
        return st.size()-1;
    }
    inline int getfail(int x, int n) {
        while (s[n-st[x].lenn-1] != s[n]) x=st[x].fail;
        return x;
    }
    inline void extend(int c, int i) {
        int cur=getfail(last, i);
        if (!st[cur].son[c]) {
            int nw=newnode(st[cur].lenn+2, st[getfail(st[cur].fail, i)].son[c]);
            st[cur].son[c]=nw;
        }
        st[ last=st[cur].son[c] ].cnt++;
    }
    void init() {
        scanf("%s", s+1);
        n=strlen(s+1);
        s[0]=0;
        newnode(0, 1), newnode(-1);
        last=0;
        rep(i, 1, n) extend(s[i]-'a', i);
    }
    ll count() {
        drep(i, st.size()-1, 0) st[st[i].fail].cnt+=st[i].cnt;
        ll ans=0;
        rep(i, 2, st.size()-1) ans=max(ans, 1LL*st[i].lenn*st[i].cnt);
        return ans;
    }}T;int main() {
    T.init();
    printf("%lld\n", T.count());}