题解 P3804 【【模板】后缀自动机 (SAM)】
很多题解都着重于 End Pos（或称Right）在SAM中的应用，当然SAM就是靠这个构建的，但是若把它换成后缀的角度去理解便会容易得多
SAM
这篇文章做不到（也不想做到）把SAM的每个东西都证一遍（真正比赛去证复杂度也没什么用），是从一个简单而非特别详细的角度去说SAM的结构和步骤
里面有一些省略的证明，取而代之的是一些用图来找规律，说明这个现象，个人感觉更能理解一些。
本蒟蒻的博客参考了这篇超好的解说，然后一些被我省略的证明这里也可以找到~
概念
1 Ep集合
End pos 集合，简称 Ep 集合，代表一个子串在原串中出现的右端点。
比如，字符串 fryakioioiakfoi 中，子串 oi 出现的位置是有红色下划线的地方：
这些红色下划线的右端点分别是第oi的 Ep 集合就是
然后，我们把 Ep 相同的子串归为一个类，叫一个等价类
一个 Ep 等价类和字符串的后缀息息相关，这就是为什么后面和 Ep 有关的几乎都可以用后缀的描述表示
所以别的博客很多都是用 Ep 集合描述地，但是个人认为后缀这一描述更容易理解
2 llen 和 lstr
llen 表示 longest lenth，lstr 表示 longest string 。
对一个 Ep 等价类，满足这个的等价类最长子串就是这个 Ep 等价类的 lstr，lstr的长度就是 llen 。
比如说，对于前面那个字符串，Ep 集合为oi ，llen 就是
3 一些结论
结论的证明别的 blog 写的已经很详细了，珂以去那里看一下。
于是，我们珂以得到
- 若子串
s 和子串t 的 Ep 集合是一样的，那么意味着s 是t 的后缀或 t 是 s 的后缀。 - 对于两个子串，他们的集合要么是包含关系，要么是没有交集。
- 对于一个等价类，里面的子串长度连续
- 等价类的数量是
O(n) 级别的，这决定了后缀自动机的复杂度
Parent 树
成功的自动机，背后都是一棵树
AC 自动机有 Trie 树，后缀自动机则有 Parent 树
概念
Parent Tree，以下简称“树”（因为只有这一个树是我们这里需要用到的）
既然我们有一些等价类，而且等价类的数量是 aababa）
根据结论2：
对于两个子串，他们的集合要么是包含关系，要么是没有交集。
互相包含的两个等价类，可以看作一个父子点对
由于不存在有交集但不包含的等价类，于是就不会存在一个点有两个父亲
我们也可以这样理解，就是一个等价类分裂成了若干个新的等价类，但是有些新的等价类不存在，就不是它的儿子
每个节点同时也对应一个字符串，就是这个类的 lstr
这样，我们得到了一个森林
看到森林，我们就想要加一个超级根 S，那个 S 的 Ep 为
这就是我们要的 Parent 树
性质
这点是使他变简单的一个重要性质：
根据上面的结论，我们可以得到树上的父亲节点的字符串，是儿子节点字符串的后缀
所以，珂以理解 parent tree 为父节点串是子节点串后缀的字符串
后缀自动机
终于到了后缀自动机了吗？是的
概念
就像 AC 自动机的点是 Trie 树的点一样，后缀自动机的点是 Parent 树的点
就像 AC 自动机的边不是 Trie 树的边一样，后缀自动机的边不是 Parent 树的边
就像 AC 自动机的边和 AC 有关（大雾），后缀自动机的边和后缀有关
一个合法的连边方案应该满足，从源点出发到达点
举个例子，原串是AABA，点中的数字代表这个点的编号，左边是后缀自动机，右边是树
这是简单的后缀自动机，然后我们看一个复杂的，原串是aababa的后缀自动机（黑边是自动机，蓝边是树，这张图还是从 这里 搬来的）
这张图的树上面已经画过了
然后我们又有一个定理，叫做
边的条数为
O(n)
这也确保了复杂度不会超标
手动构造
我们拿串AABABA举例子（应该已经很熟悉了，仍然是左边自动机，右边是树）
我们需要保证自动机的特性，而且每个前缀串的后缀是从源点出发的一条路径
先有一个空串点 1
然后加入点 2，也就是字符串为 A的点
然后加入点 3，也就是字符串 AA的点
自动机上从2连到3，然后由于树上2代表的A是AA的后缀，直接从点1连边
然后加入点 4，也就是字符串 AAB的点
自动机上先连2到3，遍历后缀，发现没有一个后缀，于是1号节点就是它的父节点
然而，我们发现A和空串都没有字符为B的出边，于是连一下，作为它们的出边为字符B的点
我们对5号点做同一个操作，只有4 号点可以连它
接下来的操作就比较让人眼花缭乱，不过仍然是一样的思路
加入6号点AABAB，和4号点一样
但是，这个自动机有一个问题：从1号点出发，有两条字符为B的边！而且，从2号点出发，也有两条字符为B的边，而这是不符合自动机的结构要求的！
由于我们的初衷是让4号串和6号串的每个后缀都出现，那么何尝不取出他们的最长公共子串呢？
先看连到7号点的边：1->7和2->7
然后看7号点连出去的边：
由于4号点的所有后缀都出现了，不连边
由于5号点还差一个后缀ABA和BA，连边7->5
然后6号点也不差后缀了，不连边
最后更新一下树，就是根节点连7号节点，然后4，6号节点做7号节点的子节点
（这里的图稍微有点问题，2->7的边的字符应该是B，不是A）
最后是串为AABABA的8号节点，同理
于是我们手动构造出了一个自动机。
用处
构造了这么久，难道SAM没有用处吗？
不，显然，由于前缀（每个节点）的后缀（从1号点出发的路径）就是子串，所以我们可以用
当然，用处不止这一种，不过说一下。
代码构造
刚刚都是手动构造，所以没用
为了更好的服务代码，我们可以实着把树搬到自动机上，而不想AC自动机把自动机搬到树上。
原因很简单，因为这里的树涉及到了修改父亲，结构不稳定，而Trie树不会修改父节点。
(再次引用那篇文章的图片)
我们形象地把下面一条链上的节点称作“地上的点”，上面的点称为“天上的点”。
这里的树的构造用存储父节点表示，要存储一个叫fa[node]的数组，代表这个节点的父节点是什么。这张图中，蓝边是node指向fa[node]。
自动机的存储用ch[node][char]的数组表示，代表点node的字符为char的出边。
把新的原串前缀str（节点编号是
自动机
1. 找后缀
找到
找到树上fa走，这就意味着遍历它所有的后缀
为什么沿着fa走就可以遍历到所有后缀呢？（修改了那篇博客里的图）
我们把每个节点的 Ep 等价类的所有字符串都写上
我们竟然发现，从点爬到根的所有字符串，就是那个点的所有后缀！
为什么呢？我们回到 Parent 树最初始的定义，是和 Ep 集合的分裂有关的。从 Ep 集合的性质出发，就可以得到这一结论。好了，其实看图就可以得出这个结论了，所以作为一个蒟蒻，证明略
为什么这就可以代表后缀自动机上的所有后缀呢？因为后缀自动机的点和 Parent 树的点是一样的，所以一个点也可以代表多个字符串，我们之前点所对应的字符串只不过是它的lstr而已
所以，我们沿着
2. 连边
我们应该怎么连边呢？我们当然是去找父节点啦
我们再假设c
那么我们就从c的出边，那么我们就添加它有一条指向c的边
如果c的边，那么直接break，因为这样代表遇到了需要新开天上的点的情况和自己的后缀已经遍历完了的情况，
Parent 树
有3种情况
情况1 根作为它的父节点
这种很好判断，从break，那么就意味着没有节点其他有资格做它的父节点，那么只有根可以，那么直接认根做父节点
情况2 别的节点做父节点
先说做法。break后的那个点c的出边指向的点
这种情况判断稍微复杂一点。我们需要知道，这个节点加上字符c之后是不是真正能作为它的后缀。我们先看一个反例。
原本我们说这是自动机的问题。现在把这个6号节点加入的过程模拟一下，我们就会发现，6号节点的父节点是4号节点！这是违背 Parent 树原则的！
到底是什么地方出错了呢？
我们发现，我们要得到的字符串，应该是这个点所对应的lstr加上c所得到的字符串。然而，现在4号点的lstr，却不是2号点的lstr加上c所得到的字符串。
那么什么是合格的点呢？
我们发现，我们要得到的字符串，应该是lstr加上c。于是我们可以字符串比较一下。这样是
然后，我们要进行优化。还记得那个llen吗？显然，y的lstr的长度应该是x的lstr的长度加一。那意味着，
所以，
情况3 要加入天上的点
这种情况的判断很简单，就是一个else
既然我们需要一个可以做
很显然，lstr应该是lstr加上c，
现在要处理
我们通过研究这两张图（从上面搬下来了）
找规律得到结论，
通过后缀的关系，我们也可以粗略地得到这个结论
具体方法，就是
总结
add(char c):
v=上次地面加入的点的编号，u=++tot, 记录u为地面加入的点
v爬树连边，直到遇到有一条字符为c的出边的点x
y=x的那条出边
若x=0:
设置fa[u]=1，退出
若len[x]+1=len[y]:
设置fa[u]=y，退出
否则：
新建天上的点p
llen[p]=llen[x]+1, fa[p]=fa[y],fa[u]=fa[y]=p
把p的出边设好
爬树找到p的入边
代码
#include<bits/stdc++.h>
using namespace std;
const int N=2000009;
char s[N];
int n,fa[N],tot=1,llen[N],ch[N][29],last=1;
int sam_add(int l,char cc){
int v=last,u=++tot,c=cc-'a';int x=v;last=u,llen[u]=l; //初始化
for(;x&&!ch[x][c];x=fa[x]) ch[x][c]=u; //爬树找x
int y=ch[x][c]; //设置y
if(x==0) return fa[u]=1; //第一种情况
else if(llen[y]==llen[x]+1) return fa[u]=y; //第二种情况
else{ //第三种情况
int p=++tot; //新建天上的点
llen[p]=llen[x]+1,fa[p]=fa[y],fa[u]=fa[y]=p; //初始化
for(int i=0;i<26;i++) ch[p][i]=ch[y][i]; //出边
for(;x&&ch[x][c]==y;x=fa[x]) ch[x][c]=p; //入边
} return 20071007;
}
int main(){
scanf("%s",s+1); n=strlen(s+1);
for(int i=1;i<=n;i++) sam_add(i,s[i]);
return 0;
}这道题目
SAM说好了
Parent树说好了
可是这道题还没说
我们关注到，其实字符串长度就是llen，我们指要求出现了几次
我们把SAM拿出来看，其实我们只需要看那个地面上的点的信息
然后那个地面上的节点在 Parent 树上做树形dp求子树中有多少个地面上的节点
为了简便dp过程，我们直接在初始化的时候只给那些地面上的点赋值即可
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=2000009;
char s[N];
int n,fa[N],tot=1,llen[N],ch[N][29],sz[N],last=1,ans;
int sam_add(int l,char cc){
int v=last,u=++tot,c=cc-'a';int x=v;last=u,sz[u]=1,llen[u]=l; //初始化
for(;x&&!ch[x][c];x=fa[x]) ch[x][c]=u; //爬树找x
int y=ch[x][c]; //设置y
if(x==0) return fa[u]=1; //第一种情况
else if(llen[y]==llen[x]+1) return fa[u]=y; //第二种情况
else{ //第三种情况
int p=++tot; //新建天上的点
llen[p]=llen[x]+1,fa[p]=fa[y],fa[u]=fa[y]=p; //初始化
for(int i=0;i<26;i++) ch[p][i]=ch[y][i]; //出边
for(;x&&ch[x][c]==y;x=fa[x]) ch[x][c]=p; //入边
} return 20071007;
}
struct edge{int to,nxt;}e[N*2]; int hd[N],cnt;
void add(int u,int v){
e[++cnt]=(edge){v,hd[u]}; hd[u]=cnt;
}
int dfs(int u){
for(int i=hd[u];i;i=e[i].nxt) sz[u]+=dfs(e[i].to);
return ans=max(ans,(sz[u]-1?llen[u]*sz[u]:ans)),sz[u];
}
int main(){
scanf("%s",s+1); n=strlen(s+1);
for(int i=1;i<=n;i++) sam_add(i,s[i]);
for(int i=1;i<=tot;i++) add(fa[i],i);
dfs(1);
printf("%d",ans);
return 0;
}