题目描述

给定一个只包含小写字母的字符串S ,

请你求出 SSS 的所有出现次数不为 1 的子串的出现次数乘上该子串长度的最大值。

输入输出格式

输入格式：

一行一个仅包含小写字母的字符串S

输出格式：

一个整数，为 所求答案

输入输出样例

输入样例#1：

abab

输出样例#1：

4

说明

对于10% 的数据，∣S∣<=1000

对于100% 的数据，∣S∣<=10^6

• 拓扑排序后边更新size，边统计答案。节点size就是字符串出现次数。
• 注意size貌似不能在ins时直接统计，可能会多一  （节点x的size  sz[x]=儿子的size之和  ，或者说是以自己为根的子树大小-1）

1 #include
      
        2 #include
       
         3 #include
        
          4 const int N=3000005; 5 int c[N][27],f[N],l[N],sz[N],you[N],dl[N],ru[N],pre=1,cnt=1,ans=0,tp=0,n; 6 char s[N>>1]; 7  8 inline void ins(int x){ 9     int p=pre,np=++cnt;pre=np;you[np]=1;l[np]=l[p]+1;10     for(;p&&!c[p][x];p=f[p])c[p][x]=np;11     if(!p)f[np]=1;12     else{13         int q=c[p][x];14         if(l[q]==l[p]+1)f[np]=q;15         else{16             int nq=++cnt;17             memcpy(c[nq],c[q],sizeof(c[q]));18             f[nq]=f[q];19             l[nq]=l[p]+1;20             f[q]=f[np]=nq;21             for(;c[p][x]==q;p=f[p]) c[p][x]=nq;22         }23     }24 }25 inline void topu(){26     for(int i=1;i<=cnt;++i)++ru[f[i]];27     for(int i=1;i<=cnt;++i)if(!ru[i])dl[++tp]=i;28     while(tp){29         int p=dl[tp];--tp;30         sz[p]+=you[p];31         if(sz[p]>1)if(l[p]*sz[p]>ans)ans=l[p]*sz[p];32         sz[f[p]]+=sz[p];33         if(!(--ru[f[p]]))dl[++tp]=f[p];34     }35 }36 int main(){37     scanf("%s",s);38     n=strlen(s);39     for(int i=0;i