怎么没有 SAM 版本的，我来补一发 www。

SAM 直接找回文串不太好找，考虑用 Manacher 找回文串，一旦有回文串我们就去 SAM 上查询。闲杂问题转化为查询S[l,r]S[l,r] 在原串中出现多少次。首先我们得找到s[l,r]s[l,r] 在 SAM 上对应的节点，这个问题是经典技巧，首先我们预处理ss 每一个位置sis_{i} 对应的 SAM 节点，记为posipos_{i}，让后我们每一次查询S[l,r]S[l,r] 从posrpos_r 开始在 Link 树往上跳，直到跳到第一个位置kk 使得lenk<r−l+1len_{k}< r-l+1，此时kk 代表的就是s[l,r]s[l,r] 对应的节点。

我们得到节点了，还有一个问题出现多少次，我们在 SAM 插入字符的时候维护一个cntcnt 表示当前节点是否是子串节点，让后在 Link 树上从下往上合并（加），让后答案就是cntk×(r−l+1)cnt_{k}\times (r-l+1) 取max⁡\max 岂可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<bits/stdc++.h>
using namespace std;
constexpr int MN=1e6+15;
int n,m,r[MN],poss[MN];
long long ans;
int pre[31][MN];
char p[MN];
string s;

struct SAM{
    int nxt[MN][26],len[MN],c[MN],cnt[MN],id[MN],pos[MN],fa[MN],tot,lst;

    void init(){
        tot=lst=1;
    }

    int newnode(){
        int cur=++tot;
        memset(nxt[cur],0,sizeof(nxt[cur]));
        return cur;
    }

    int clone(int from){
        int cur=newnode();
        fa[cur]=fa[from];
        memcpy(nxt[cur],nxt[from],sizeof(nxt[from]));
        return cur;
    }

    void expand(int c){
        int cur=newnode();
        len[cur]=len[lst]+1;
        cnt[cur]=1;
        int p=lst;
        while(p&&!nxt[p][c]) nxt[p][c]=cur,p=fa[p];
        if(!p){
            fa[cur]=1;
        }else{
            int q=nxt[p][c];
            if(len[q]==len[p]+1){
                fa[cur]=q;
            }else{
                int nq=clone(q);
                len[nq]=len[p]+1;
                fa[cur]=fa[q]=nq;
                while(p&&nxt[p][c]==q){
                    nxt[p][c]=nq,p=fa[p];
                }
            }
        }
        lst=cur;
    }

    void getsiz(){
        for(int i=1;i<=tot;i++) c[len[i]]++;
        for(int i=1;i<=n;i++) c[i]+=c[i-1];
        for(int i=1;i<=tot;i++) id[c[len[i]]--]=i;
        for(int i=tot;i>=1;i--){
            cnt[fa[id[i]]]+=cnt[id[i]];
        }
    }

    void initst(){
        for(int i=1;i<=tot;i++) pre[0][i]=fa[i];
        for(int i=1;i<=30;i++){
            for(int j=1;j<=tot;j++){
                pre[i][j]=pre[i-1][pre[i-1][j]];
            }
        }
    }

    void find(int l,int r){
        if(l<1||r>n) return;
        int slen=r-l+1,now=pos[r];
        for(int i=30;i>=0;i--){
            if(pre[i][now]&&len[pre[i][now]]>=slen) now=pre[i][now];
        }
        ans=max(ans,1ll*cnt[now]*(r-l+1));
    }
    
}sam;

void manacher(){
    p[++m]='@';
    for(int i=1;i<=n;i++){
        p[++m]='#';
        p[++m]=s[i];
        poss[m]=i;
    }
    p[++m]='#',p[++m]='$';
    int pos=0,mx=0;
    for(int i=1;i<=m;i++){
        if(i<mx) r[i]=min(mx-i,r[pos*2-i]);
        else r[i]=1;
        sam.find(poss[i-r[i]+2],poss[i+r[i]-2]);
        while(p[i-r[i]]==p[i+r[i]]){
            r[i]++;
            sam.find(poss[i-r[i]+2],poss[i+r[i]-2]);
        }
        if(i+r[i]>mx){
            mx=i+r[i],pos=i;
        }
    }
}

signed main(){
    cin>>s;
    sam.init();
    n=s.length();
    s=" "+s;
    for(int i=1;i<=n;i++){
        sam.expand(s[i]-'a');
        sam.pos[i]=sam.lst;
    }
    sam.initst();
    sam.getsiz();
    manacher();
    cout<<ans;

    return 0;
}