String Cheese
小F有一个字符串 (S) 和一个初始为空的字符串 (T) ，以及一个初始为 (0) 的变量 (c) 。他会不断重复进行以下两步操作，直到 (T) 的长度超过 (S) 时结束：
-
在 (T) 的开头或者结尾任意添加一个字符。
-
设 (T) 在 (S) 中作为子串出现了 (k) 次，则执行操作 (c = c + k) 。
小F想知道，如果合理地进行第一步操作，操作结束时 (c) 所能达到的最大值是多少。
对于所有数据保证 (1le |S|le 5 imes 10^5) ，且 (S) 中仅包含小写字母。
题解
首先我们可以限制任何时刻(T)都要是(S)的子串，然后设(dp(T))表示从串(T)开局的最大答案。任意实现一个能子串判重的算法就可以暴力转移做到(O(n^2sigma))。后面大写字母一律代表某字符串，小写字母一律
代表某字符。
构建出(S)的后缀自动机。可以证明如果(right(aX)=right(X))则对于任意(Y)都有(right(aXY)=right(XY))，所以对于当前串(T)如果存在(a)使得(right(T)=right(aT))则一定存在一种最优方案第一步选择在左边添加(a)，而这也就是后缀自动机上节点代表的最长串。所以我们的
转移边有两种，一种是向后加字符，可以沿着后缀自动机走；一种是向前加字符，可以沿着parent link走，每次走到一个点直接扩展到最大长度就行了，这两者都可以按拓扑序倒序算dp值，复杂度就是构建后缀自动机的复杂度。
CO int N=1e6;
int last=1,tot=1;
array<int,26> ch[N];
int fa[N],len[N],siz[N];
void extend(int c){
int x=last,cur=last=++tot;
len[cur]=len[x]+1,siz[cur]=1;
for(;x and !ch[x][c];x=fa[x]) ch[x][c]=cur;
if(!x) {fa[cur]=1; return;}
int y=ch[x][c];
if(len[y]==len[x]+1) {fa[cur]=y; return;}
int clone=++tot;
ch[clone]=ch[y],fa[clone]=fa[y],len[clone]=len[x]+1;
fa[cur]=fa[y]=clone;
for(;ch[x][c]==y;x=fa[x]) ch[x][c]=clone;
}
char str[N];
int cnt[N],ord[N];
int64 dp[N];
int main(){
scanf("%s",str+1);
int n=strlen(str+1);
for(int i=1;i<=n;++i) extend(str[i]-'a');
for(int i=1;i<=tot;++i) ++cnt[len[i]];
for(int i=1;i<=n;++i) cnt[i]+=cnt[i-1];
for(int i=1;i<=tot;++i) ord[cnt[len[i]]--]=i;
for(int i=tot;i>=2;--i) siz[fa[ord[i]]]+=siz[ord[i]];
dp[1]=0;
for(int i=1;i<=tot;++i){
int x=ord[i];
dp[x]=max(dp[x],dp[fa[x]]+(int64)(len[x]-len[fa[x]])*siz[x]);
for(int c=0;c<26;++c)if(ch[x][c])
dp[ch[x][c]]=max(dp[ch[x][c]],dp[x]+(int64)(len[ch[x][c]]-len[x])*siz[ch[x][c]]);
}
write(dp[last],'
');
return 0;
}