洛谷3804

题目描述

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

请你求出

输入输出格式

输入格式：

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

输出格式：

一个整数，为所求答案

输入输出样例

输入样例#1： 复制

abab

输出样例#1： 复制

说明

对于

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

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

 1 #include<cstring>
 2 #include<cstdio>
 3 #include<iostream>
 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<n;++i)ins(s[i]-'a');
40     topu();
41     printf("%d",ans);
42     return 0;
43 }