Portal

这里介绍一种全新的后缀数组解法。

定义：sa、rk、ht数组，即为SA里的常规数组。

我们依旧求出ht数组，并利用单调栈（可以参见[AHOI2013]差异的题解或者本人的后缀数据结构学习笔记）求出每个位置最多可以向左向右分别延伸到多远。即，(L_i,R_i)为满足(\min\limits_{j=L_i+1}^{R_i-1}ht_j)\geq ht_i的最大区间。则串s[sa_i,\dots,sa_i+ht_i-1]共出现了R_i-L_i次。

这里是求出(L_i,R_i)的代码:

L[0]=stk[0]=1;
for(int i=2;i<=n;i++){
    while(tp&&ht[stk[tp]]>ht[i])R[stk[tp--]]=i;
    if(ht[stk[tp]]==ht[i])L[i]=L[stk[tp]];
    else L[i]=stk[tp];
    stk[++tp]=i;
}
while(tp)R[stk[tp--]]=n+1;

（事实上，我们求出这个数组的目的，就是为了得到R_i-L_i，即它的出现次数）

然后，对于每个i，我们HASH+二分出来s[sa_i,\dots,sa_i+ht_i-1]的前缀中，最长的回文串长度。则（长度*出现次数），即可与答案取\max。

这里我们先解答几个问题：

Q1：为什么一定要是前缀回文串？s[sa_i,\dots,sa_i+ht_i-1]的任何子串不都出现了R_i-L_i次吗？

A1:确实，这里是应该用它的全部子串。但是，我们不要忘记，它的每个子串，都是某一条后缀的前缀！所以，总有一条后缀，会计算它的非前缀子串的。并且，在这里计算的话，它出现的次数也会少于它真实的出现次数，毕竟这里是要求s[sa_i,\dots,sa_i+ht_i-1]这一整个字符串全都出现，但是如果只讨论该字符串的子串的话，出现次数也会更多。

Q2：那既然讨论子串时次数会更多，为什么要在这里讨论它的前缀呢？说不定它的前缀的出现次数也会更多呢？

A2：确实，它的次数确实会更多。我们把前缀的合法区间设为(L',R')，则必有(L_i,R_i)\subset(L',R')。但是，我们设(L',R')中\min的位置为p，则必有(L_p,R_p)=(L',R')！因此，这个前缀的贡献，会在p处被计算，在那时的(L_p,R_p)即是它真实的出现次数。

这里是二分+HASH的写法：

for(int i=2;i<=n;i++){
    int tms=R[i]-L[i];
    int l=0,r=ht[i];
    while(l<r){
        int mid=(l+r+1)>>1;
        if((pre[sa[i]+mid-1]-pre[sa[i]-1])==(suf[sa[i]+ht[i]-mid]-suf[sa[i]+ht[i]]))l=mid;
        else r=mid-1;
    }
    res=max(res,1ll*tms*l);
}

当然，以某个位置开头的最长回文串长度，是可以使用ManacherO(1)求出的，这里因为懒得推了就使用HASH吧。

但是，如果你带入第一组样例算的话，会发现算出来的结果是6，而非7。

为什么呢？

因为所有只出现一次的回文串都不会被统计上！

所以我们只需再跑一遍Manacher求回文串最大长度即可。不会的可以参见本人的Manacher感性瞎扯。

复杂度O(n\log n)。

代码（SA+HASH+Manacher模板三合一，你值得拥有）：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int x[400100],y[400100],sa[400100],ht[400100],rk[400100],buc[400100],n,m;
int L[400100],R[400100],stk[400100],tp;
char s[400100],str[800100];
ll res;
bool mat(int a,int b,int k){
    if(y[a]!=y[b])return false;
    if((a+k<=n)^(b+k<=n))return false;
    if((a+k<=n)&&(b+k<=n))return y[a+k]==y[b+k];
    return true;
}
void SA(){
    for(int i=1;i<=n;i++)buc[x[i]=s[i]]++;
    for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
    for(int i=n;i;i--)sa[buc[x[i]]--]=i;
    for(int k=1;k<=n;k<<=1){
        int num=0;
        for(int i=n-k+1;i<=n;i++)y[++num]=i;
        for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
        for(int i=1;i<=m;i++)buc[i]=0;
        for(int i=1;i<=n;i++)buc[x[y[i]]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n;i;i--)sa[buc[x[y[i]]]--]=y[i],y[i]=0;
        swap(x,y);
        x[sa[1]]=num=1;
        for(int i=2;i<=n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
        m=num;
    }
    for(int i=1;i<=n;i++)rk[sa[i]]=i;
    for(int i=1,k=0;i<=n;i++){
        if(rk[i]==1)continue;
        if(k)k--;
        int j=sa[rk[i]-1];
        while(j+k<=n&&i+k<=n&&s[j+k]==s[i+k])k++;
        ht[rk[i]]=k;
    }
}
typedef unsigned long long ull;
ull sd1=998244353,sd2=666623333,pov1[401000],pov2[401000];
struct HASH{
    ull val1,val2;
    int len;
    HASH(){
        val1=val2=0ull;
        len=0;
    }
    HASH(char ip){
        val1=val2=ip;
        len=1;
    }
    friend HASH operator +(const HASH &x,const HASH &y){
        HASH z;
        z.val1=x.val1*pov1[y.len]+y.val1;
        z.val2=x.val2*pov2[y.len]+y.val2;
        z.len=x.len+y.len;
        return z;
    }
    friend HASH operator -(const HASH &x,const HASH &y){
        HASH z;
        z.val1=x.val1-y.val1*pov1[x.len-y.len];
        z.val2=x.val2-y.val2*pov2[x.len-y.len];
        z.len=x.len-y.len;
        return z;
    }
    friend bool operator ==(const HASH &x,const HASH &y){
        if(x.len!=y.len)return false;
        if(x.val1!=y.val1)return false;
        if(x.val2!=y.val2)return false;
        return true;
    }
}pre[401000],suf[800100];
int Centre,Rpos,rad[800100],S;
void prep(){
    str[S++]='#';
    for(int i=1;i<=n;i++)str[S++]=s[i],str[S++]='#';
}
void Manacher(){
    Centre=Rpos=-1;
    for(register int i=0;i<S;i++){
        rad[i]=(i<Rpos)?min(Rpos-i,rad[Centre*2-i]):1;
        while(i+rad[i]<S&&i-rad[i]>=0)if(str[i+rad[i]]==str[i-rad[i]])rad[i]++;else break;
        if(i+rad[i]>Rpos)Rpos=i+rad[i],Centre=i;
        res=max(res,1ll*rad[i]-1);
    }
}
int main(){
    scanf("%s",s+1),n=strlen(s+1),m='z',pov1[0]=pov2[0]=1;
    for(int i=1;i<=n;i++)pov1[i]=pov1[i-1]*sd1,pov2[i]=pov2[i-1]*sd2;
    for(int i=1;i<=n;i++)pre[i]=pre[i-1]+HASH(s[i]);
    for(int i=n;i>=1;i--)suf[i]=suf[i+1]+HASH(s[i]);
    SA();
//  for(int i=1;i<=n;i++)printf("%d ",rk[i]);puts("");
//  for(int i=1;i<=n;i++)printf("%d ",ht[i]);puts("");
    L[0]=stk[0]=1;
    for(int i=2;i<=n;i++){
        while(tp&&ht[stk[tp]]>ht[i])R[stk[tp--]]=i;
        if(ht[stk[tp]]==ht[i])L[i]=L[stk[tp]];
        else L[i]=stk[tp];
        stk[++tp]=i;
    }
    while(tp)R[stk[tp--]]=n+1;
    for(int i=2;i<=n;i++){
        int tms=R[i]-L[i];
        int l=0,r=ht[i];
        while(l<r){
            int mid=(l+r+1)>>1;
            if((pre[sa[i]+mid-1]-pre[sa[i]-1])==(suf[sa[i]+ht[i]-mid]-suf[sa[i]+ht[i]]))l=mid;
            else r=mid-1;
        }
        res=max(res,1ll*tms*l);
    }
    prep();
    Manacher();
//  for(int i=0;i<S;i++)printf("%c ",str[i]);puts("");
//  for(int i=0;i<S;i++)printf("%d ",rad[i]);puts("");
    printf("%lld\n",res);
    return 0;
}