建出parent树统计即可。开始memcpy处写的是sizeof(son[y])，然后就T掉了……还是少用这种东西吧。
同时也有SA做法。答案子串一定是名次数组中相邻两个串的lcp。单调栈统计其是几个后缀的前缀即可。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 2000010 int n,cnt,last,son[N][26],fail[N],size[N],len[N],t=0,p[N]; struct data{int to,nxt; }edge[N]; void ins(int c) { int x=++cnt,p=last;last=x;len[x]=n;size[x]=1; while (!son[p][c]&&p) son[p][c]=x,p=fail[p]; if (!p) fail[x]=1; else { int q=son[p][c]; if (len[q]==len[p]+1) fail[x]=q; else { int y=++cnt; len[y]=len[p]+1; memcpy(son[y],son[q],sizeof(son[q])); fail[y]=fail[q],fail[x]=fail[q]=y; while (son[p][c]==q) son[p][c]=y,p=fail[p]; } } } void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;} void dfs(int k) { for (int i=p[k];i;i=edge[i].nxt) { dfs(edge[i].to); size[k]+=size[edge[i].to]; } } int main() { #ifndef ONLINE_JUDGE freopen("suffixautomaton.in","r",stdin); freopen("suffixautomaton.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif last=cnt=1; char c=getchar(); while (c>='a'&&c<='z') n++,ins(c-97),c=getchar(); for (int i=2;i<=cnt;i++) addedge(fail[i],i); dfs(1); long long ans=0; for (int i=1;i<=cnt;i++) if (size[i]>1) ans=max(ans,1ll*size[i]*len[i]); cout<<ans; return 0; }