虽然是第二次学后缀自动机，这个学习的过程在我看来仍然是学习过程中最困难的，因为这个东西比较抽象，应用的性质很多，即使是构造理解起来也十分困难。另外，讲解这个东西的博客都太长了，一个一个写着预计阅读时间一个小时？而且看一句就要好好想一会，不时还要往上翻，晦涩的定义也太多了让人产生抗拒。
首先先不管太多，搞懂\(SAM\)的在线构建。
代码如下：
int x=++tot;
len[x]=len[u]+1;size[x]=1;
for(;u&&trans[u][c]==0;u=fa[u])trans[u][c]=x;
if(u==0)fa[x]=1;
else{
int v=trans[u][c];
if(len[v]==len[u]+1)fa[x]=v;
else{
int w=++tot;len[w]=len[u]+1;
fa[w]=fa[v];fa[x]=fa[v]=w;
memcpy(trans[w],trans[v],sizeof(trans[v]));
for(;u&&trans[u][c]==v;u=fa[u])trans[u][c]=w;
}
}
u=x;
虽然但是，直接看代码还是不太明智。
首先要对\(SAM\)有一个印象。
想必看这篇博客的人都知道AC自动机。
在\(trie\)树上加上了\(fail\)边就成了\(AC\)自动机。
在\(parent\)树上加了一些\(trans\)边就成了\(SAM\)。
字符串"aababa"的parent树长这样
（PS：图是从上面链接中蒯的）
设字符串\(s\)在原串中所有结束位置的集合为\(Ep(s)\)
一个点代表一个子串的类，一个类中的子串\(s_i\)满足\(Ep(s_i)\)相同，也可以说这个点代表了这个相同的\(Ep(s_i)\)。
如\(a\)在原串中结尾的位置为\((1,2,4,6)\)、\(ababa\)和\(aababa\)在原串结尾位置都是\((6)\)
所以图中\((1,2,4,6)\)点代表的类是\(\{a\}\)，图中\((6)\)点代表的类是\(\{baba,ababa,aababa\}\)。
根节点相当于一个虚拟节点。
几个十分重要的也是显然的性质：
1、不同的子串的\(Ep(s_i)\)不是包含就是没有交集。所以一个类的儿子是这个类的子集，一个类不能有两个父亲（这里把节点当做集合看了）
2、一个类中的字符串如果有多个那一定是连续差一个字符的。（如上图中(6)的类中\(“aababa“\)是\(”ababa"\)多一个\(”a"\)，\(“ababa"\)是\(”baba"\)多一个\(“b"\)）
3、一个类中最短字符串长度是父亲类中最长字符串长度+1。
4、一个节点父亲类中的串是这个节点类中串的后缀。
\(trans\)边要满足从根开始沿着\(trans\)边走到任意一点经过的\(trans\)上字符连起来是原串的一个子串。
\(SAM\)就是\(parent\)树上的点与\(trans\)边构成的有向无环图（并不算上\(parent\)树的边）。
接下来解释构建\(SAM\)的代码。
\(SAM\)在每次插入一个字符c之后维护
我们除去辅助数据之外其实只关心两个东西，也就是\(SAM\)的两个部分：\(parent\)树上的点，\(trans\)边。
int x=++tot;
len[x]=len[u]+1;size[x]=1;
为了方便说话，把插入\(c\)之前的串叫做旧串，把插入\(c\)之后的串叫做新串（比如构建\(“aababa”\)的\(SAM\)时现在插入最后一个\(a\)，\(“aabab”\)是旧串，\(“aababa"\)是新串）。
\(x\)是新加入一个字符\(c\)之后新的\(parent\)树的节点。\(len[x]\)是节点\(x\)代表类中子串的最长长度。
\(size[x]\)是广义\(SAM\)的内容先不用管，\(u\)是包含旧串的类。
为什么一定有新的节点？设插入前字符串长度为\(n\)，上面说到\(parent\)树的节点代表一个子串类，新加入一个字符之后，以\(n+1\)位置结尾的类不存在所以一定有新的节点。
for(;u&&trans[u][c]==0;u=fa[u])trans[u][c]=x;
\(fa[u]\)是\(u\)在\(parent\)树上的父亲。考虑一直这样跳父亲的意义，其实这是在遍历所有后缀。
考虑把\(trans[u][c]\)设成\(x\)代表什么？代表u中字符串可以通过在后边加上一个字符\('c'\)成为\(x\)节点代表的串。显然，在插入一个字符之后需要修改的\(trans[u][c]\)的\(u\)只可能是代表旧串的后缀的类，即u的祖先。
if(u==0)fa[x]=1;
遍历了全部的祖先包括代表空串的根节点之后还是没有向\(c\)转移的边，说明\(c\)从来没有出现过。直接把\(x\)接到根上。因为c都没出现过其他的类必然不可能会包含\(n+1\)这个结束位置，所以只能接在代表全集的根上才能满足性质1——一个类的儿子是这个类的子集
int v=trans[u][c];
if(len[v]==len[u]+1)fa[x]=v;
\(len[v]==len[u]+1\)这个判断是板子里最难以理解的。
\(len[v]=len[u]+1\)代表了什么？\(len[v]!=len[u]+1\)代表了什么？
当\(len[v]!=len[u]+1\)时
\(len[u]\)不可能比\(len[v]\)大（考虑trans的意义），说明\(len[v]>len[u]+1\)。因为\(tran[u][c]\)的定义，\(u\)中最长的串加上\(c\)之后一定是\(v\)中最长串的后缀
图中是\(len[v]=len[u]+1+2\)的情形，可见这个\(v\)节点包含了三个字符串，其中长度大于\(len[u]+1\)的两个串结尾位置不能包含\(n+1\),因为前面找到的\(u\)是可以在其代表串之后加c的最长后缀,之前出现的串中，不存在长度比\(len[u\)]更大的串可以满足在之后加上\('c'\)结尾位置也就不可能为\(n+1\)。所以我们要做的是把这个代表三个串的节点分成一个长度为\(len[u]+1\)的节点\(w\)它的结尾位置可以为\(n+1\)和两个长度大于\(len[u]\)的节点\(v\)它们的结尾位置不能为\(n+1\),然后把\(x\)和\(v\)连在\(w\)上。
所以\(len[u]+1==len[v]\)时就直接把\(x\)连在\(v\)上，因为结尾位置\(n+1\)被\(v\)类包含。
就是这个代码
if(len[v]==len[u]+1)fa[x]=v;
else{
int w=++tot;len[w]=len[u]+1;
fa[w]=fa[v];fa[x]=fa[v]=w;
memcpy(trans[w],trans[v],sizeof(trans[v]));
for(;u&&trans[u][c]==v;u=fa[u])trans[u][c]=w;
}
至此后缀自动机的构造结束。
广义后缀自动机就是满足多个串的后缀自动机。
struct SAM{
int trans[N][30],cnt,head[N],tot,u,size[N],len[N],fa[N];
struct edge{
int to,nxt;
}e[N];
void add_edge(int u,int v){
cnt++;
e[cnt].nxt=head[u];
e[cnt].to=v;
head[u]=cnt;
}
void init(){tot=u=1;}
void rebuild(){u=1;}
void ins(int c){
if(trans[u][c]){
int v=trans[u][c];
if(len[v]==len[u]+1)size[v]++,u=v;
else{
int x=++tot;
size[x]=1;
len[x]=len[u]+1;
memcpy(trans[x],trans[v],sizeof(trans[x]));
fa[x]=fa[v];fa[v]=x;
for(;u&&trans[u][c]==v;u=fa[u])trans[u][c]=x;
u=x;
}
}
else{
int x=++tot;
len[x]=len[u]+1;size[x]=1;
for(;u&&trans[u][c]==0;u=fa[u])trans[u][c]=x;
if(u==0)fa[x]=1;
else{
int v=trans[u][c];
if(len[v]==len[u]+1)fa[x]=v;
else{
int w=++tot;len[w]=len[u]+1;
fa[w]=fa[v];fa[x]=fa[v]=w;
memcpy(trans[w],trans[v],sizeof(trans[v]));
for(;u&&trans[u][c]==v;u=fa[u])trans[u][c]=w;
}
}
u=x;
}
}
}
模板的代码只是多了一个判断，跟普通的后缀自动机差不多。