题意

给定一个字符串，求一个回文子串，使得它的长度×出现次数最大

思路

回文自动机

学了之后再来补坑qwq

---

后缀自动机SAM

参（zhao）考（ban）STO

对原串建SAM，然后跑manacher，对于每个回文串，在SAM询问出现次数，求最大值即可

由于直接在SAM上面询问是O(n)的，这样做实际上是\(n^2\)的，于是考虑在parent树上倍增

记fa[ i ][ j ]为i节点向上跳\(2^j\)步后的位置，由于在parent树上的一个节点的父亲表示的串是这个节点表示的串的后缀，所以对于一个串[ L , R ]，从pos[ R ]这个节点开始向上跳，使得len>=R-L+1的最小节点即为所求，它的size数组即为出现次数

注意这道题fa数组不能开太大，否则会MLE

Code：

#include
    
     #define N 600005using namespace std;typedef long long ll;char a[N];int n,ndsum=1,las=1,root=1;int sz[N],tot[N],rk[N],pos[N];int len,p[N];int fa[N][21];ll ans=0;struct Node{    int ch[26],par,len;}s[N];void add_sam(int w,int i){    int x=++ndsum,tmp=las; sz[x]=1;    pos[i]=x;    s[x].len=s[tmp].len+1;    for(;!s[tmp].ch[w];tmp=s[tmp].par) s[tmp].ch[w]=x;    if(!tmp) s[x].par=root;    else    {        int B=s[tmp].ch[w];        if(s[tmp].len+1==s[B].len) s[x].par=B;        else        {            int nb=++ndsum;            s[nb]=s[B];            s[nb].len=s[tmp].len+1;            s[B].par=s[x].par=nb;            for(;s[tmp].ch[w]==B;tmp=s[tmp].par) s[tmp].ch[w]=nb;        }    }    las=x;}void manacher_init(){    for(int i=n;i>=1;--i) a[i*2+1]='#',a[i*2]=a[i-1];    a[0]=a[1]='#';    len=2*n+2;}void manacher(){    manacher_init();    int maxr=0,mid;    for(int i=0;i
     
      i) p[i]=min(maxr-i,p[(mid<<1)-i]);        else p[i]=1;        while(a[i+p[i]]==a[i-p[i]]) ++p[i];        if(i+p[i]-1>maxr) {maxr=i+p[i]-1;mid=i;}    }}void init(){    for(int i=1;i<=ndsum;++i)    {        int x=rk[i];        fa[x][0]=s[x].par;        for(int j=1;j<=20;++j) fa[x][j]=fa[fa[x][j-1]][j-1];    }}int query(int l,int r){    int now=pos[r];    for(int i=20;i>=0;--i)        if(s[fa[now][i]].len>=r-l+1)             now=fa[now][i];    return sz[now];}int main(){    scanf("%s",a); n=strlen(a);    for(int i=0;i
      
       =1;--i) sz[s[rk[i]].par]+=sz[rk[i]];    sz[1]=0;    init();    for(int i=2;i
       
        >1)-1,half=(p[i]>>1)-1;        ans=max(ans,(ll)(p[i]-1)*query(x-half,x+half));    }    for(int i=3;i
        
         >1)-1,half=(p[i]-1)>>1;        ans=max(ans,(ll)(p[i]-1)*query(x-half+1,x+half));    }    cout<
         
          <