首先一个结论：串\(S\)中本质不同的回文串个数最多有\(|S|\)个
证明考虑以点\(i\)结尾的所有回文串，假设为\(S[l_1,i],S[l_2,i],...,S[l_k,i]\)，其中\(l_1 < l_2 < ... < l_k\)，那么因为\(S[l_i,i]\)是个回文串，所以\(S[l_2,i] = S[l_1,l_1 + i - l_2]\)，那么这个串可以在以点\(l_1 + i - l_2\)结尾的字符串中被考虑到，当前无需考虑。所以对于以\(i\)结尾的所有串，只有\(S[l_1,i]\)需要考虑。所以以\(i\)结尾的所有回文串至多会生成出一个本质不同的回文串，所以至多有\(|S|\)个本质不同的回文串。
跑一边\(Manacher\)将上面的\(S[l_1,i]\)中的\(l_1\)计算出来，然后在\(SA\)里计算一下与\(suf_{l_1}\)的LCP大于等于\(i - l_1 + 1\)的后缀数量，就是这个串在\(S\)中的出现次数。
#include<iostream>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<iomanip>
//This code is written by Itst
using namespace std;
const int MAXN = 3e5 + 7;
char s[MAXN];
int L;
namespace SA{
int pot[MAXN << 1] , rk[MAXN << 1] , sa[MAXN] , tp[MAXN << 1] , h[MAXN];
int maxN , logg2[MAXN] , ST[21][MAXN];
void sort(int p){
memset(pot , 0 , sizeof(int) * (maxN + 1));
for(int i = 1 ; i <= L ; ++i)
++pot[rk[i]];
for(int i = 1 ; i <= maxN ; ++i)
pot[i] += pot[i - 1];
for(int i = 1 ; i <= L ; ++i)
sa[++pot[rk[tp[i]] - 1]] = tp[i];
swap(tp , rk);
for(int i = 1 ; i <= L ; ++i)
rk[sa[i]] = rk[sa[i - 1]] + (tp[sa[i]] != tp[sa[i - 1]] || tp[sa[i] + p] != tp[sa[i - 1] + p]);
maxN = rk[sa[L]];
}
void init_ST(){
for(int i = 2 ; i <= L ; ++i)
logg2[i] = logg2[i >> 1] + 1;
for(int i = 2 ; i <= L ; ++i)
ST[0][i] = h[i];
for(int i = 1 ; 1 << i <= L - 1 ; ++i)
for(int j = 2 ; j + (1 << i) - 1 <= L ; ++j)
ST[i][j] = min(ST[i - 1][j] , ST[i - 1][j + (1 << (i - 1))]);
}
void init(){
scanf("%s" , s + 1);
L = strlen(s + 1);
maxN = 26;
for(int i = 1 ; i <= L ; ++i)
rk[tp[i] = i] = s[i] - 'a' + 1;
sort(0);
for(int i = 1 ; maxN != L ; i <<= 1){
int cnt = 0;
for(int j = 1 ; j <= i ; ++j)
tp[++cnt] = L - i + j;
for(int j = 1 ; j <= L ; ++j)
if(sa[j] > i)
tp[++cnt] = sa[j] - i;
sort(i);
}
for(int i = 1 ; i <= L ; ++i){
if(rk[i] == 1) continue;
int t = rk[i];
h[t] = max(0 , h[rk[i - 1]] - 1);
while(s[sa[t] + h[t]] == s[sa[t - 1] + h[t]])
++h[t];
}
init_ST();
}
int qST(int x , int y){
if(x > y) x ^= y ^= x ^= y;
int t = logg2[y - x + 1];
return min(ST[t][x] , ST[t][y - (1 << t) + 1]);
}
long long work(int pos , int len){
int ansL , l = 1 , r = rk[pos];
while(l < r){
int mid = (l + r) >> 1;
qST(mid + 1 , rk[pos]) >= len ? r = mid : l = mid + 1;
}
ansL = l;
l = rk[pos]; r = L;
while(l < r){
int mid = (l + r + 1) >> 1;
qST(rk[pos] + 1 , mid) >= len ? l = mid : r = mid - 1;
}
return 1ll * (r - ansL + 1) * len;
}
}
namespace manacher{
int maxL[MAXN << 1] , minL[MAXN];
char S[MAXN << 1];
void work(){
for(int i = 1 ; i <= L ; ++i)
S[(i << 1) - 1] = s[i];
int maxR = 0 , maxI = 1;
for(int i = 1 ; i < (L << 1) ; ++i){
int l = min(maxL[2 * maxI - i] , maxR - i);//曾经把min写成了max。。。
while(l <= i && i + l <= (L << 1) && S[i - l] == S[i + l])
++l;
maxL[i] = l;
if(l + i > maxR){
maxR = l + i;
maxI = i;
}
}
memset(minL , 0x3f , sizeof(minL));
for(int i = 1 ; i < (L << 1) ; ++i)
minL[(maxL[i] + i - 1) >> 1] = min(minL[(maxL[i] + i - 1) >> 1] , ((i - maxL[i] + 1) >> 1) + 1);
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
SA::init();
manacher::work();
long long ans = 0;
for(int i = 1 ; i <= L ; ++i)
if(manacher::minL[i] <= i)
ans = max(ans , SA::work(manacher::minL[i] , i - manacher::minL[i] + 1));
cout << ans;
return 0;
}