PAM
样题

// CREATED BY MASHIROYUKI

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#define IO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define rep(i, x, n) for(int i = x; i <= n; i ++ )
#define downrep(i, x, n) for(int i = n; i >= x; i -- )
#define pb(x) push_back(x)
#define all(x) x.begin(),x.end()
#define ls (u<<1)
#define rs (u<<1|1)
#define ll long long
#define db double
#define INF 0x3f3f3f3f
#define mod 1e9+7
template<typename T> void dbg(const T&x) {cout<<x<<' ';}
template<typename T,typename...Args> void dbg(const T&x,const Args&...rest) {
    cout<<x<<' ';dbg(rest...);
}
template<typename T> 
void read(T &x) {
    x=0;int f=1;char ch;
    for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    x*=f; 
}
template<typename T,typename...Args> void read(T &x,Args&...rest) {
    read(x);read(rest...);
}
const int N=1e6+10,maxn=3e5+10;
struct PAM {
    int idx,last,tot;//idx表示节点下标，n-1结尾的最长回文串
    int cnt[maxn],len[maxn],fail[maxn],son[maxn][26];//len表示每个回文串的长度
    char s[maxn];
    int node(int l) {
        ++idx;
        memset(son[idx],0,sizeof son[idx]);
        len[idx]=l;
        cnt[idx]=fail[idx]=0;
        return idx;
    }
    void clear() {
        idx=-1;
        last=0;
        s[0]='$'; //边界处理
        node(0); //偶数回文串根节点
        node(-1); //奇数回文串根节点
        fail[0]=1;
    }
    int getfail(int x) {
        while(s[tot-len[x]-1]!=s[tot]) x=fail[x];
        return x;
    }
    void insert(char c) {
        s[++tot]=c;
        int now=getfail(last);
        if(!son[now][c-'a']) {
            int x=node(len[now]+2);
            fail[x]=son[getfail(fail[now])][c-'a'];
            son[now][c-'a']=x;
        }
        last=son[now][c-'a'];
        cnt[last]++;
    } 
    ll solve() {
        downrep(i,1,idx) cnt[fail[i]]+=cnt[i];
        ll ans=0;
        rep(i,1,idx) ans=max(ans,1ll*len[i]*cnt[i]); //每个节点都是本质不同的节点
        return ans;
    }
} pam;

char s[maxn];
void solve() {
    pam.clear();
    scanf("%s",s+1);
    for(int i=1;s[i];i++) pam.insert(s[i]);
    printf("%lld\n",pam.solve());
}

signed main() {
    solve();
}

回文树中的每个节点只代表了所有本质不同回文串（就是不考虑下标不同），然后每条fail边 指向当前回文串的最长回文后缀，如果没有就指向0