浅谈后缀自动机
虽然是第二次学后缀自动机，这个学习的过程在我看来仍然是学习过程中最困难的，因为这个东西比较抽象，应用的性质很多，即使是构造理解起来也十分困难。另外，讲解这个东西的博客都太长了，一个一个写着预计阅读时间一个小时？而且看一句就要好好想一会，不时还要往上翻，晦涩的定义也太多了让人产生抗拒。
写得真的好
我知道了它为什么叫SAM
本文面向初步了解SAM的人，通过对论文suffix_automata的翻译的解读加深对SAM的理解。
后缀自动机
后缀自动机可以理解为一个串所有子串的简明信息，其空间复杂度为O(n)，构建的复杂度为O(n)
后缀自动机的英文为\(suffix\ automata\)或者单词的有向无环图\("direcged\ acyclic\ word\ graph"\)简写为\(”DWAG"\)
后缀自动机的定义
对字符串s的后缀自动机是一个最小化确定有限状态自动机，它能接受s的所有后缀。
对后缀自动机定义的解释：
首先对确定有限状态自动机的概念解释：
1、一个有向无环图，其中节点代表一个状态，而边代表了状态的转移。
2、某一个状态\(t_0\)被称为是初始状态，从这个状态经过若干次转移可以到达所有的状态。
3、每一个转移（有向图中的每一条边），都有一个标记（字母），从某一个状态出发的转移不能有相同的标记。下面这种情况是不允许的。
4、有若干个终止状态。
后缀自动机上从\(t_0\)开始按某一个路径转移到终止状态，顺序写出这个路径上转移上的标记（也就是字母）之后得到的串是串\(S\)的一个后缀。
所有符合以上特征的自动机中，后缀自动机拥有最少的状态数。
后缀自动机的最简性
即从\(t_0\)开始的某一条路径唯一代表着S一个子串（这里不是从\(t_0\)开始到一个终止状态，而是到任意一个点），同时S的一个子串唯一地由从\(t_0\)开始的某一条路径表示。
我们称从\(t_0\)开始的任意一条路径匹配（一对一）了S中的一个子串。
但是一个状态可能对应这很多条从\(t_0\)开始的路径。
一个线性构建后缀自动机的方法
在这之前必须要介绍一些性质，这对理解这个构建的方法是不可缺少的。
结束位置endpos及其性质
考虑字符串\(s\)中的一个子串\(t\)，\(t\)的所有结束位置的集合为\(endpos(t)\)
对于所有\(endpos\)相同的\(t_i\)，我们将它们归位一个等价类。
这跟后缀自动机有什么关系？其实后缀自动机中的一个状态就是这里的一个等价类。其最简性由迈希尔-尼罗德定理证明
引理1：S的两个非空子串u、v（lenght(u)
证明显然（狗头）
所以一个类中不能有两个相同长度的串。
引理2：考虑两个非空字符串类u、w（lenght(u)
证明显然（狗头）
如果u是w的后缀那么u的终点集合包含w的终点集合。
引理3：考虑一个终点等价类，将该等价类中的字符串按长度从大到小排序，每一个字符串是上一个串的后缀并且长度是上一个串长度-1。或者说这个等价类中的串长度连续。
考虑这个等价类中的任意两个串u，v(lenght(u)
后缀链接
通过对endpos的性质的分析，我们知道所有有着相同终点集合的点存在于一个等价类中，并且设w为这个类u中最长的字符串，这个类中其他的串是这个串的连续后缀。其他后缀在另外的若干个等价类中。
令u后缀链接link(u)代表不在这个类中的最长的w的后缀所在的类。
换言之，u的后缀链接link(u)指向在不同等价类中的w的最长后缀所在的类。
特别地，我们让初始状态\(t_0\)是一个特别地类中，其对应的终点集合是全集，可以理解为这个类中的子串是空串。
引理4：后缀链接构成了一个以\(t_0\)为根的树。
任取一点u，不停地找不在这个类中最长后缀（u=link(u)），这个后缀的长度单调减少，最后一定会到代表空串的\(t_0\)
其实这颗树就是parent树
引理5：一个类（树中的一个节点），的儿子都是这个类终点集合的不相交子集。
结合引理2和引理4。
总结这两个引理：后缀链接形成一棵以\(t_0\)为根的树，而这棵树事实上是所有终点集合的树状包含关系。
其他定义及性质
定义：每个状态u对应一个或多个字符串，我们记longest(u)是其中最长者，len(u)是其长度。我们记shortest(u)是这些字符串中的最短者，其长度为minlen(u)。
1、引理2可以改写成：一状态u对应的所有字符串是longest(u)的不同后缀，并且包括[minlen(u),len(u)]之间的所有长度。
2、后缀链接的定义可以改写成：对每个状态u≠\(t_0\)定义的后缀链接指向的状态对应longest(u)的长度为minlen(u)-1的后缀。
一些性质：minlen(u)和link(u)的关系表示如下：minlen(u)=len(link(u))+1。 如果我们从任意节点\(u\)开始沿后缀链接移动，我们早晚会到达初始状态t_0.在此情况下，我们得到了一系列不相交的区间[minlen(\(u_i\)),len(\(u_i\))]，其并集是一个连续区间。
代码
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;
一个具体的后缀链接的例子，字符串"aababa"的parent树（也就是后缀链接形成的树）长这样
（PS：图是从上面链接中蒯的）
\(trans\)边要满足从根开始沿着\(trans\)边走到任意一点经过的\(trans\)上字符连起来是原串的一个子串。考虑把\(trans[u][c]\)设成\(x\)代表什么？代表u中某一个字符串可以通过在后边加上一个字符\('c'\)成为\(x\)节点中的某一个的串。进一步的代表u中所有字符串可以在x中找到后面加上一个字符\('c'\)的串，即令u的字符串类为s1，x的字符串为s2，\(s1+'c'\in s2\)
\(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\)树的节点，x节点目前代表新串的所有后缀。
\(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]\)的\(u\)只可能是代表旧串的后缀的类，即\(u\)的祖先。
现在x节点代表新串的所有后缀，显然新串的所有后缀加上字符'c'之后都包含于x的类，结合trans[u][c]的定义所以如果\(trans[u][c]\)为0的话就将其设为x。
if(u==0)fa[x]=1;
遍历了全部的祖先包括代表空串的根节点之后还是没有向\(c\)转移的边，说明\(c\)从来没有出现过。直接把\(x\)接到根上。因为c都没出现过，其他的类必然不可能会包含\(n+1\)这个结束位置，所以只能接在代表全集的根上才能满足引理5：一个类（树中的一个节点），的儿子都是这个类终点集合的不相交子集
相反如果存在一个u，说明c这个字符出现过。
int v=trans[u][c];
if(len[v]==len[u]+1)fa[x]=v;
\(len[v]==len[u]+1\)这个判断是板子里最难以理解的。
u是什么，v是什么？
u是包含trans[u][c]不为0的旧串最长后缀的类。结合u的意义v就是包含曾经出现过的新串的最长后缀的类，这个类中最长的串不一定是曾经出现过的新串的最长后缀。
\(len[v]=len[u]+1\)代表了什么？\(len[v]!=len[u]+1\)代表了什么？
当\(len[v]!=len[u]+1\)时
\(len[u]\)不可能比\(len[v]\)大（结合trans[u][c]的定义，u最长的串加上c之后的串一定在v中），说明\(len[v]>len[u]+1\)。
图中是\(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;
}
}
}
模板的代码只是多了一个判断，跟普通的后缀自动机差不多。
状态的数量
从代码看出来，每次加入一个字符之后状态最多加2，所以状态数最多是2N+1
不从代码的角度分析，由性质5可以得出最多parent树最多有n个叶子节点，然后推出状态数最多是2*N-1
构建算法的时间复杂度
for(;u&&trans[u][c]==0;u=fa[u])trans[u][c]=x;
for(;u&&trans[u][c]==v;u=fa[u])trans[u][c]=w;
纯属口胡
复杂度主要是这里，只对这两行代码分析即可。
设shortlen[x]代表x中字符串最短长度。
先考虑第一个for
每跳一次，stortlen[u]最少减少1。
如果存在w
shortlen[fa[x]]=shortlen[w]=shortlen[u]+1
这显然是线性的。
如果不存在2
shortlen[fa[x]]=shortlen[v]=shortlen[u]+1
这显然是线性的。
之后考虑第二个for
如果存在w
考虑shortlen[fa[x]]，shortlen[fa[x]]=shortlen[w]<=shortlen[u]+1<=shortlen[fa[last]]+1
如果不存在w
shortlen[fa[x]]=shortlen[v]<=shortlen[u]+1<=shortlen[fa[last]]+1
shortlen[fa[x]]最多等于shortlen[fa[last]]+1,每次上溯次数跟shortlen[fa[last]]减少同阶。
所以是线性的。
后缀树根后缀自动机的联系
将一个串的所有后缀扔进一个trie中，然后对节点进行压缩，这样的树就是后缀树。
首先我们假定输入的字符串的每一个后缀都在后缀树中对应了一个节点（这对于任意的字符串不一定成立，如“aaaa...”），在后缀树的经典实现中，通过在后缀树的末位加上一个特殊字符如“#”来保证这点。
令rev[s]代表s串反写，DAWG[s]代表由字符串s建立的后缀自动机，ST[s]代表s的后缀树。
我们介绍“扩展指针”的概念：对于树节点v和字符c，ext[c,v]指向树中对应于字符串c+v(注意这里顺序)的节点（如果路径c+v在某边的终点结束，那就将其指向该边的较低点）；如果这样一条路径c+v不在树中，那么扩展指针未定义。在某种意义上，扩展指针的对立面就是后缀链接。
定理1 DAWG[s]中的后缀链接就是ST[rev[s]]
定理2 DAWG[s]的边都能用后缀树ST[rev[s]]的扩展指针表示。另外，DAWG[s]中的连续转移就是ST[rev[s]]中反向的后缀指针
定理3 使用后缀自动机DAWG[s]，我们可以用O(n)的时间构建后缀树ST[rev[]s))。
定理4 使用后缀树ST[rev[s]]，我们可以用O(n)的时间构建后缀自动机DAWG(s)。
证明显然（狗头）
所以一个类中不能有两个相同长度的串。
引理2：考虑两个非空字符串类u、w（lenght(u)
证明显然（狗头）
如果u是w的后缀那么u的终点集合包含w的终点集合。
引理3：考虑一个终点等价类，将该等价类中的字符串按长度从大到小排序，每一个字符串是上一个串的后缀并且长度是上一个串长度-1。或者说这个等价类中的串长度连续。
考虑这个等价类中的任意两个串u，v(lenght(u)
后缀链接
通过对endpos的性质的分析，我们知道所有有着相同终点集合的点存在于一个等价类中，并且设w为这个类u中最长的字符串，这个类中其他的串是这个串的连续后缀。其他后缀在另外的若干个等价类中。
令u后缀链接link(u)代表不在这个类中的最长的w的后缀所在的类。
换言之，u的后缀链接link(u)指向在不同等价类中的w的最长后缀所在的类。
特别地，我们让初始状态\(t_0\)是一个特别地类中，其对应的终点集合是全集，可以理解为这个类中的子串是空串。
引理4：后缀链接构成了一个以\(t_0\)为根的树。
任取一点u，不停地找不在这个类中最长后缀（u=link(u)），这个后缀的长度单调减少，最后一定会到代表空串的\(t_0\)
其实这颗树就是parent树
引理5：一个类（树中的一个节点），的儿子都是这个类终点集合的不相交子集。
结合引理2和引理4。
总结这两个引理：后缀链接形成一棵以\(t_0\)为根的树，而这棵树事实上是所有终点集合的树状包含关系。
其他定义及性质
定义：每个状态u对应一个或多个字符串，我们记longest(u)是其中最长者，len(u)是其长度。我们记shortest(u)是这些字符串中的最短者，其长度为minlen(u)。
1、引理2可以改写成：一状态u对应的所有字符串是longest(u)的不同后缀，并且包括[minlen(u),len(u)]之间的所有长度。
2、后缀链接的定义可以改写成：对每个状态u≠\(t_0\)定义的后缀链接指向的状态对应longest(u)的长度为minlen(u)-1的后缀。
一些性质：minlen(u)和link(u)的关系表示如下：minlen(u)=len(link(u))+1。 如果我们从任意节点\(u\)开始沿后缀链接移动，我们早晚会到达初始状态t_0.在此情况下，我们得到了一系列不相交的区间[minlen(\(u_i\)),len(\(u_i\))]，其并集是一个连续区间。
代码
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;
一个具体的后缀链接的例子，字符串"aababa"的parent树（也就是后缀链接形成的树）长这样
（PS：图是从上面链接中蒯的）
\(trans\)边要满足从根开始沿着\(trans\)边走到任意一点经过的\(trans\)上字符连起来是原串的一个子串。考虑把\(trans[u][c]\)设成\(x\)代表什么？代表u中某一个字符串可以通过在后边加上一个字符\('c'\)成为\(x\)节点中的某一个的串。进一步的代表u中所有字符串可以在x中找到后面加上一个字符\('c'\)的串，即令u的字符串类为s1，x的字符串为s2，\(s1+'c'\in s2\)
\(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\)树的节点，x节点目前代表新串的所有后缀。
\(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]\)的\(u\)只可能是代表旧串的后缀的类，即\(u\)的祖先。
现在x节点代表新串的所有后缀，显然新串的所有后缀加上字符'c'之后都包含于x的类，结合trans[u][c]的定义所以如果\(trans[u][c]\)为0的话就将其设为x。
if(u==0)fa[x]=1;
遍历了全部的祖先包括代表空串的根节点之后还是没有向\(c\)转移的边，说明\(c\)从来没有出现过。直接把\(x\)接到根上。因为c都没出现过，其他的类必然不可能会包含\(n+1\)这个结束位置，所以只能接在代表全集的根上才能满足引理5：一个类（树中的一个节点），的儿子都是这个类终点集合的不相交子集
相反如果存在一个u，说明c这个字符出现过。
int v=trans[u][c];
if(len[v]==len[u]+1)fa[x]=v;
\(len[v]==len[u]+1\)这个判断是板子里最难以理解的。
u是什么，v是什么？
u是包含trans[u][c]不为0的旧串最长后缀的类。结合u的意义v就是包含曾经出现过的新串的最长后缀的类，这个类中最长的串不一定是曾经出现过的新串的最长后缀。
\(len[v]=len[u]+1\)代表了什么？\(len[v]!=len[u]+1\)代表了什么？
当\(len[v]!=len[u]+1\)时
\(len[u]\)不可能比\(len[v]\)大（结合trans[u][c]的定义，u最长的串加上c之后的串一定在v中），说明\(len[v]>len[u]+1\)。
图中是\(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;
}
}
}
模板的代码只是多了一个判断，跟普通的后缀自动机差不多。
状态的数量
从代码看出来，每次加入一个字符之后状态最多加2，所以状态数最多是2N+1
不从代码的角度分析，由性质5可以得出最多parent树最多有n个叶子节点，然后推出状态数最多是2*N-1
构建算法的时间复杂度
for(;u&&trans[u][c]==0;u=fa[u])trans[u][c]=x;
for(;u&&trans[u][c]==v;u=fa[u])trans[u][c]=w;
纯属口胡
复杂度主要是这里，只对这两行代码分析即可。
设shortlen[x]代表x中字符串最短长度。
先考虑第一个for
每跳一次，stortlen[u]最少减少1。
如果存在w
shortlen[fa[x]]=shortlen[w]=shortlen[u]+1
这显然是线性的。
如果不存在2
shortlen[fa[x]]=shortlen[v]=shortlen[u]+1
这显然是线性的。
之后考虑第二个for
如果存在w
考虑shortlen[fa[x]]，shortlen[fa[x]]=shortlen[w]<=shortlen[u]+1<=shortlen[fa[last]]+1
如果不存在w
shortlen[fa[x]]=shortlen[v]<=shortlen[u]+1<=shortlen[fa[last]]+1
shortlen[fa[x]]最多等于shortlen[fa[last]]+1,每次上溯次数跟shortlen[fa[last]]减少同阶。
所以是线性的。
后缀树根后缀自动机的联系
将一个串的所有后缀扔进一个trie中，然后对节点进行压缩，这样的树就是后缀树。
首先我们假定输入的字符串的每一个后缀都在后缀树中对应了一个节点（这对于任意的字符串不一定成立，如“aaaa...”），在后缀树的经典实现中，通过在后缀树的末位加上一个特殊字符如“#”来保证这点。
令rev[s]代表s串反写，DAWG[s]代表由字符串s建立的后缀自动机，ST[s]代表s的后缀树。
我们介绍“扩展指针”的概念：对于树节点v和字符c，ext[c,v]指向树中对应于字符串c+v(注意这里顺序)的节点（如果路径c+v在某边的终点结束，那就将其指向该边的较低点）；如果这样一条路径c+v不在树中，那么扩展指针未定义。在某种意义上，扩展指针的对立面就是后缀链接。
定理1 DAWG[s]中的后缀链接就是ST[rev[s]]
定理2 DAWG[s]的边都能用后缀树ST[rev[s]]的扩展指针表示。另外，DAWG[s]中的连续转移就是ST[rev[s]]中反向的后缀指针
定理3 使用后缀自动机DAWG[s]，我们可以用O(n)的时间构建后缀树ST[rev[]s))。
定理4 使用后缀树ST[rev[s]]，我们可以用O(n)的时间构建后缀自动机DAWG(s)。
证明显然（狗头）
如果u是w的后缀那么u的终点集合包含w的终点集合。
引理3：考虑一个终点等价类，将该等价类中的字符串按长度从大到小排序，每一个字符串是上一个串的后缀并且长度是上一个串长度-1。或者说这个等价类中的串长度连续。
考虑这个等价类中的任意两个串u，v(lenght(u) 通过对endpos的性质的分析，我们知道所有有着相同终点集合的点存在于一个等价类中，并且设w为这个类u中最长的字符串，这个类中其他的串是这个串的连续后缀。其他后缀在另外的若干个等价类中。 令u后缀链接link(u)代表不在这个类中的最长的w的后缀所在的类。 特别地，我们让初始状态\(t_0\)是一个特别地类中，其对应的终点集合是全集，可以理解为这个类中的子串是空串。 任取一点u，不停地找不在这个类中最长后缀（u=link(u)），这个后缀的长度单调减少，最后一定会到代表空串的\(t_0\) 结合引理2和引理4。 定义：每个状态u对应一个或多个字符串，我们记longest(u)是其中最长者，len(u)是其长度。我们记shortest(u)是这些字符串中的最短者，其长度为minlen(u)。 一个具体的后缀链接的例子，字符串"aababa"的parent树（也就是后缀链接形成的树）长这样 \(trans\)边要满足从根开始沿着\(trans\)边走到任意一点经过的\(trans\)上字符连起来是原串的一个子串。考虑把\(trans[u][c]\)设成\(x\)代表什么？代表u中某一个字符串可以通过在后边加上一个字符\('c'\)成为\(x\)节点中的某一个的串。进一步的代表u中所有字符串可以在x中找到后面加上一个字符\('c'\)的串，即令u的字符串类为s1，x的字符串为s2，\(s1+'c'\in s2\) \(SAM\)就是\(parent\)树上的点与\(trans\)边构成的有向无环图（并不算上\(parent\)树的边）。 接下来解释构建\(SAM\)的代码。 为了方便说话，把插入\(c\)之前的串叫做旧串，把插入\(c\)之后的串叫做新串（比如构建\(“aababa”\)的\(SAM\)时现在插入最后一个\(a\)，\(“aabab”\)是旧串，\(“aababa"\)是新串）。 \(x\)是新加入一个字符\(c\)之后新的\(parent\)树的节点，x节点目前代表新串的所有后缀。 \(len[x]\)是节点\(x\)代表类中子串的最长长度。 \(size[x]\)是广义\(SAM\)的内容先不用管，\(u\)是包含旧串的类。 为什么一定有新的节点？设插入前字符串长度为\(n\)，上面说到\(parent\)树的节点代表一个子串类，新加入一个字符之后，只以\(n+1\)为位置结尾的类不存在，所以一定有新的节点。 \(fa[u]\)是\(u\)在\(parent\)树上的父亲。这是在遍历所有后缀。在插入一个字符之后需要修改的\(trans[u][c]\)的\(u\)只可能是代表旧串的后缀的类，即\(u\)的祖先。 遍历了全部的祖先包括代表空串的根节点之后还是没有向\(c\)转移的边，说明\(c\)从来没有出现过。直接把\(x\)接到根上。因为c都没出现过，其他的类必然不可能会包含\(n+1\)这个结束位置，所以只能接在代表全集的根上才能满足引理5：一个类（树中的一个节点），的儿子都是这个类终点集合的不相交子集 相反如果存在一个u，说明c这个字符出现过。 \(len[v]==len[u]+1\)这个判断是板子里最难以理解的。 u是什么，v是什么？ 当\(len[v]!=len[u]+1\)时 至此后缀自动机的构造结束。 广义后缀自动机就是满足多个串的后缀自动机。 模板的代码只是多了一个判断，跟普通的后缀自动机差不多。 从代码看出来，每次加入一个字符之后状态最多加2，所以状态数最多是2N+1 不从代码的角度分析，由性质5可以得出最多parent树最多有n个叶子节点，然后推出状态数最多是2*N-1 纯属口胡 先考虑第一个for 之后考虑第二个for shortlen[fa[x]]最多等于shortlen[fa[last]]+1,每次上溯次数跟shortlen[fa[last]]减少同阶。 所以是线性的。 将一个串的所有后缀扔进一个trie中，然后对节点进行压缩，这样的树就是后缀树。 首先我们假定输入的字符串的每一个后缀都在后缀树中对应了一个节点（这对于任意的字符串不一定成立，如“aaaa...”），在后缀树的经典实现中，通过在后缀树的末位加上一个特殊字符如“#”来保证这点。 令rev[s]代表s串反写，DAWG[s]代表由字符串s建立的后缀自动机，ST[s]代表s的后缀树。 我们介绍“扩展指针”的概念：对于树节点v和字符c，ext[c,v]指向树中对应于字符串c+v(注意这里顺序)的节点（如果路径c+v在某边的终点结束，那就将其指向该边的较低点）；如果这样一条路径c+v不在树中，那么扩展指针未定义。在某种意义上，扩展指针的对立面就是后缀链接。后缀链接
换言之，u的后缀链接link(u)指向在不同等价类中的w的最长后缀所在的类。引理4：后缀链接构成了一个以\(t_0\)为根的树。
其实这颗树就是parent树引理5：一个类（树中的一个节点），的儿子都是这个类终点集合的不相交子集。
总结这两个引理：后缀链接形成一棵以\(t_0\)为根的树，而这棵树事实上是所有终点集合的树状包含关系。其他定义及性质
1、引理2可以改写成：一状态u对应的所有字符串是longest(u)的不同后缀，并且包括[minlen(u),len(u)]之间的所有长度。
2、后缀链接的定义可以改写成：对每个状态u≠\(t_0\)定义的后缀链接指向的状态对应longest(u)的长度为minlen(u)-1的后缀。
一些性质：minlen(u)和link(u)的关系表示如下：minlen(u)=len(link(u))+1。 如果我们从任意节点\(u\)开始沿后缀链接移动，我们早晚会到达初始状态t_0.在此情况下，我们得到了一系列不相交的区间[minlen(\(u_i\)),len(\(u_i\))]，其并集是一个连续区间。代码
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;
（PS：图是从上面链接中蒯的）
\(SAM\)在每次插入一个字符c之后维护
我们除去辅助数据之外其实只关心两个东西，也就是\(SAM\)的两个部分：\(parent\)树上的点，\(trans\)边。 int x=++tot;
len[x]=len[u]+1;size[x]=1;
for(;u&&trans[u][c]==0;u=fa[u])trans[u][c]=x;
现在x节点代表新串的所有后缀，显然新串的所有后缀加上字符'c'之后都包含于x的类，结合trans[u][c]的定义所以如果\(trans[u][c]\)为0的话就将其设为x。if(u==0)fa[x]=1;
int v=trans[u][c];
if(len[v]==len[u]+1)fa[x]=v;
u是包含trans[u][c]不为0的旧串最长后缀的类。结合u的意义v就是包含曾经出现过的新串的最长后缀的类，这个类中最长的串不一定是曾经出现过的新串的最长后缀。
\(len[v]=len[u]+1\)代表了什么？\(len[v]!=len[u]+1\)代表了什么？
\(len[u]\)不可能比\(len[v]\)大（结合trans[u][c]的定义，u最长的串加上c之后的串一定在v中），说明\(len[v]>len[u]+1\)。
图中是\(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;
}
}
}
状态的数量
构建算法的时间复杂度
for(;u&&trans[u][c]==0;u=fa[u])trans[u][c]=x;
for(;u&&trans[u][c]==v;u=fa[u])trans[u][c]=w;
复杂度主要是这里，只对这两行代码分析即可。
设shortlen[x]代表x中字符串最短长度。
每跳一次，stortlen[u]最少减少1。
如果存在w
shortlen[fa[x]]=shortlen[w]=shortlen[u]+1
这显然是线性的。
如果不存在2
shortlen[fa[x]]=shortlen[v]=shortlen[u]+1
这显然是线性的。
如果存在w
考虑shortlen[fa[x]]，shortlen[fa[x]]=shortlen[w]<=shortlen[u]+1<=shortlen[fa[last]]+1
如果不存在w
shortlen[fa[x]]=shortlen[v]<=shortlen[u]+1<=shortlen[fa[last]]+1后缀树根后缀自动机的联系
定理1 DAWG[s]中的后缀链接就是ST[rev[s]]
定理2 DAWG[s]的边都能用后缀树ST[rev[s]]的扩展指针表示。另外，DAWG[s]中的连续转移就是ST[rev[s]]中反向的后缀指针
定理3 使用后缀自动机DAWG[s]，我们可以用O(n)的时间构建后缀树ST[rev[]s))。
定理4 使用后缀树ST[rev[s]]，我们可以用O(n)的时间构建后缀自动机DAWG(s)。