开个坑，花点时间学学 SAM。
一些概念
1.
SAM 是个自动机，而且是个 DAG。
SAM 有一个初始节点 \(u\)，从 \(u\) 出发的任意一条路径都对应原串 \(S\) 的一个子串，且原串 \(S\) 的任意一个子串唯一对应一条 \(u\) 出发的路径。
SAM 的优秀之处在于它压缩了很多相似的后缀信息。
2.
有一个很重要的概念就是 endpos 集合，定义 \(endpos(T)\) 是串 \(T\) 在 \(S\) 中的所有出现位置的结尾下标（从 \(1\) 开始标号）。
我们会发现会有一些 \(T\) 他们的 endpos$是相同的，比如令 \(S=abab\) 则 \(endpos(ab)=endpos(b)\)。
如果两个不同的串 \(T_1,T_2\) 同时在 \(x\) 处结尾出现，那必定有较短的那个是较长的那个的后缀。
所以对于两个串 \(X,Y\)，我们假设 \(|X|\le |Y|\)，则：如果 \(X\) 是 \(Y\) 的后缀，容易得 \(endpos(Y)\subseteq endpos(X)\)，否则 \(endpos(X) \cap endpos(Y)=\empty\)。
我们把所有 endpos 相同的子串拿出来称为一个等价类：考察一个等价类的所有串，按照长度从大到小排序以后记作 \(T_1,T_2,...,T_k\)。
根据上面的内容我们可以发现 \(T_k\) 是 \(T_{k-1}\) 的后缀，而 \(T_{k-2}\) 是 \(T_k\) 的后缀，以此类推。
更一般的，显然所有 \(T_i\) 都是 \(T_1\) 的后缀且 \(|T_i|=|T_1|-i+1\)。
所以一个 endpos 等价类实际上就是若干个后缀压缩成了一起，我们用 \(T_1\) 来代表这个等价类。
3.
SAM 想做到的一点是：每个节点（状态）都代表了一个完整的 endpos 等价类。
在构建 SAM 之前，我们还需要引入一个东西：parent tree。
我们知道一个节点 \(x\) 对应一个等价类：\(T_1,T_2,...,T_k\)，我们定义 \(T'\) 是 \(T_k\) 去掉开头字符的结果（也就是所谓的 \(T_{k+1}\)）。
定义 \(link(x)\) 是 \(T_{k+1}\) 所属的等价类的对应节点。
显然 \(link(x)\rightarrow x\) 连边会形成一颗 \(u\) 为根的树，这个就是 parent tree。
而且你会发现 \(endpos(T)\) 一定是 \(endpos(T')\) 的真子集。
另外我们可以发现兄弟节点的 \(endpos\) 一定是交集为空的，因为他们没有后缀关系。（比如 \(ba\) 和 \(ca\) 的父亲都是 \(a\)，那么 \(endpos(ba)\cap endpos(ca)\) 显然为空）。
而且可以说明的是不同的等价类只有 \(O(n)\) 个，因为这就是一个集合分拆的过程啊。
4.
SAM 就是在线地同时构建出 parent tree 和 DFA 本身。
考虑我们建出了 \(S\) 的 SAM，怎么求 \(S+c\) 的 SAM。
我们本质上只增加了 \(|S|+1\) 个以最后一个字符结尾的子串（也就是此时形成的所有后缀），而且你考虑有些后缀应该是已经出现过的，如果长度为 \(x\) 的后缀出现过了那么长度为 \(y\le x\) 的后缀一定出现过了。
这个 \(x-suffix\) 其实就是 \(link(S+c)\) 啊，因为 \(endpos(S+c)\) 显然就是 \(\{|S|+1\}\)。
所以考虑先求 \(link(S+c)\)。
从 \(link(S)\) 不断跳 parent tree（其实就是从大往小枚举后缀，只不过每次会处理一段连续的性质相似的后缀罢了），当跳到一个点 \(p\)，它的 \(nxt(c)\) 已经有值，我们设 \(p\) 所在的等价类，最长的那个串是 \(a\)，那么 \(a+c\) 就一定就是最长的出现过了的后缀。
设 \(p\) 跳转到了 \(q\)，如果 \(len(q)=len(p)+1\) 那么直接 \(link(S+c)=q\)。这里 \(len(a)\) 表示的是节点 \(a\) 所代表的等价类里最长的串长。
如果不然，也就是 \(len(q)\gt len(p)+1\)，那么说明 \(a+c\) 只是 \(q\) 等价类的一个非最长串，你不能让 \(link(S+c)=q\)，因为 \(q\) 集合的最长串并不是 \(S+c\) 的后缀。
此时等价类 \(q\) 实质上被分为了两部分：长度在 \((len(p)+1,len(q)]\) 这段的串的 endpos 不变，而 \((len(link(q)),len(p)+1]\) 这些长度的串的 endpos 应该多了一个位置 \(|S|+1\) 啊。
所以这就是两个等价类了，我们新建一个节点 \(r\)，那么 \(link(r)\) 变为原先的 \(link(q)\) 而 \(link(q)\) 变为 \(r\) 且 \(len(r)=len(p)+1\)。
然后 \(nxt_r\) 肯定是照搬 \(nxt_q\) 的，而且我们继续从 \(p\) 跳 parent tree：所有 \(nxt(c)=q\) 的都要改成 \(nxt(c)=r\) 了，最后 \(link(S+c)=r\) 完事。
感觉描述起来挺烦的但理解以后并不难记难写。
另外关于求 endpos 啊。我们计算完 \(S\) 对应的节点后，在该节点的 endpos 集合中加入 \(|S|\) 这个数，然后一个节点的真实 endpos 应该是 parent tree 中，所有子树的并，所以可以建出 SAM 以后线段树合并。
一些例题
求一个串 \(S\) 中所有出现次数大于 \(1\) 的子串的：出现次数 * 长度的最大值。
\(|S|\le 10^6\)。
出现次数大于 \(1\) 也就是 \(|endpos|\gt 1\) 且我们注意到对于一个 endpos 等价类我们其实只关注 \(len(x)\)，也就是里面最长的那个串。
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN=1e6+10,MAXC=30;
char s[MAXN];
int n;
ll ans;
struct Node{int fa,len,nxt[MAXC];};
namespace SAM{
Node t[MAXN*2];
vector<int>e[MAXN*2];
int sz,lst,siz[MAXN*2];
void init(){
rep(i,0,sz)e[i].clear();
sz=lst=0;
memset(t[0].nxt,0,sizeof t[0].nxt);
t[0].fa=-1;t[0].len=0;
}
int newnode(){
sz++;
memset(t[sz].nxt,0,sizeof t[sz].nxt);
return sz;
}
void extend(int ch){
int cur=newnode();t[cur].len=t[lst].len+1;siz[cur]=1;
int p=lst;
while(p!=-1 && !t[p].nxt[ch]){
t[p].nxt[ch]=cur;
p=t[p].fa;
}
if(p==-1){
t[cur].fa=0;
}else{
int q=t[p].nxt[ch];
if(t[q].len==t[p].len+1)t[cur].fa=q;
else{
int r=newnode();
rep(j,0,25)t[r].nxt[j]=t[q].nxt[j];
t[r].len=t[p].len+1;
t[r].fa=t[q].fa;
while(p!=-1 && t[p].nxt[ch]==q){
t[p].nxt[ch]=r;
p=t[p].fa;
}
t[q].fa=t[cur].fa=r;
}
}
lst=cur;
}
void build(){
rep(i,1,sz)e[t[i].fa].push_back(i);
}
void dfs(int u){
for(auto v:e[u])dfs(v),siz[u]+=siz[v];
if(siz[u]>1)ans=max(ans,1ll*siz[u]*t[u].len);
}
};
int sz[MAXN*2];
vector<int>res;
int main(){
cin>>(s+1);
n=strlen(s+1);
SAM::init();
rep(i,1,n){
SAM::extend(s[i]-'a');
}
SAM::build();
SAM::dfs(0);
cout<<ans;
return 0;
}
SAM 很强大啊，能干的事情非常多，先咕了。
标签：nxt,SAM,后缀,len,学习,link,笔记,endpos From： https://www.cnblogs.com/Cry-For-theMoon/p/16936801.html