简单介绍了后缀自动机的构建和性质，用于帮助记忆而非学习……
变量声明
Right(s): 子串s出现位置右端点的集合
一个节点（或状态）是所有Right相同的字符串组成的集合
Right(x)：节点x任意一个串的Right
len(x)：节点x中长度最大字符串的长度
pre(x):Parent树上x的父亲，表示Right(x)是其子集，且len最大的节点
ch(x,c)：x节点加入字符c后到达的节点
后缀自动机的根节点(空串)记为rt
构建SAM
加入第i个字符c产生的子串:
1、Right={i}，记做np
2、Right≠{i}，记做nq
上一次插入的np节点记做las
第一类
需要找到所有{i-1}∈Right的节点。Right={i-1}的节点是las，只需从las不断跳pre，设当前跳到的节点是p。有三种情况：
① ch(p,c)=null 不存在p加入c的转移，直接加入这个转移:ch(p,c)=np,p=pre(p)
② ch(p,c)=q 转入第二类
③ p=rt。那Right包含Right(np)的就只有空串了。所以pre(np)=rt
第二类
此时p加入c的转移已经存在。
① 若len(p)+1=len(q) 因为p是las在Parent树上的祖先，所以p的每个串都是las串的后缀。len(p)+1=len(q)，从而q的每个串都可以由p中一个串加入c后得到，而las中的每个串加入c后都转移到np，可知Right(np)∈Right(q)，所以pre(np)=q。
② 若len(p)+1≠len(q) 不是q的每个串都可以由p中一个串加入c后得到。能得到的是那些len<=len(p)+1的串。此时把q拆成q和nq两个节点，使nq节点满足①代替掉原来的q，pre(q)=nq再调整原先的ch关系即完成插入。
性质
1、在SAM中节点数不超过2n−2，边数不超过3n−3
2、从一节点开始跳pre，Right集合变大，字符串长度变短
3、一节点表示的字符串是其Parent树上子孙表示字符串的后缀
4、节点x表示字符串长度的连续区间是[len(fa(x))+1,len(x)]
5、两个串的最长公共后缀,位于这两个串对应状态在Parent树上的最近公共祖先状态
子串的出现次数
节点x中字符串出现的次数是以x为根的子树中字符串出现次数之和。
np产生的节点出现次数为1，nq产生的节点出现次数为0。根据len计数排序+拓扑就可以了。
广义后缀自动机
将多个串建在同一个后缀自动机上。只需要插入完一个串之后las=rt即可。
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int n,m;
char s[N];
namespace SAM {
int tot=1,las=1,rt=1;
int len[N],siz[N],pre[N],ch[N][26],rad[N],ord[N];
inline int Nw(int l,int v) {
++tot;
len[tot]=l; siz[tot]=v;
return tot;
}
inline void Insert(int x) {
int p=las,np=las=Nw(len[p]+1,1);
while (!ch[p][x]) ch[p][x]=np,p=pre[p];
if (!p) pre[np]=rt;
else {
int q=ch[p][x],nq;
if (len[p]+1==len[q]) pre[np]=q;
else {
nq=Nw(len[p]+1,0);
memcpy(ch[nq],ch[q],sizeof(ch[q]));
pre[nq]=pre[q]; pre[q]=pre[np]=nq;
while (ch[p][x]==q) ch[p][x]=nq,p=pre[p];
}
}
}
inline void Getcnt() {
for (int i=1;i<=tot;i++) rad[len[i]]++;
for (int i=1;i<=tot;i++) rad[i]+=rad[i-1];
for (int i=1;i<=tot;i++) ord[rad[len[i]]--]=i;
for (int i=tot;i;i--) siz[pre[ord[i]]]+=siz[ord[i]];
}
}
using namespace SAM;
int main() {
scanf("%s",s+1); n=strlen(s+1);
for (int i=1;i<=n;i++) Insert(s[i]-'a');
Getcnt();
long long ans=0;
for (int i=1;i<=tot;i++) {
if (siz[i]>1) ans=max(ans,1LL*siz[i]*len[i]);
}
printf("%lld",ans);
return 0;
}