“辽望猎风焚烧的原野，在一夜之间，化为灰烬。”
后缀自动机
后缀自动机（），一个快捷简便的字符串数据结构，用于处理多种类型的字符串问题。能够在线性空间和线性时间内完成大部分问题。
后缀自动机是一种 ，由两部分组成，这两部分的状态集合相等，但转移函数集合不同，且相互关联，区分开来，我们称之为 和 。
是一个 ，其性质在于从 开始到任意一个状态之间的所有转移函数的组成一定是当前字符串的子串。关于这个，我们可以在 的状态数下很轻松地解决这个问题。但很显然的， 可以在 的时空内解决。
定义
终止集合
对于一个字符串 ，存在一个集合 表示当前字符串在母串中出现的所有位置的终止位置。举一个例子：
母串为 aabababbabbababaa，对于 ，则是 ，因为 babab 在母串中一共出现过两次，分别在：
而对应的最后一个标号则是 和 ，需要注意的是 是一个集合。
等价类
对于两个子串 ，如果存在 ，则称 和 为等价类。很显然的，对于上面那个例子而言，babab,abab 是等价类，而 bab 并不是，因为 。
endpos的性质
引理
对于字符串 ，如果存在 ，这里假设 ，每一次 在母串中的出现，都是以 的后缀形式出现。
更清晰地说，如果 且 ，则 一定是 的后缀。
引理
对于任意 个子串 ,设定 ，一定存在：
这个可以和上面那个进行类比，读者进行一波理解（我也不是很能讲清楚）。
引理
对于一个 等价类，将这个类中的所有字符串按照长度排序，计最短的字符串为 ，最长的为 ，则其长度刚好覆盖区间 ，且任意两个字符串，较短者为较长者的后缀。
后缀链接
定义一个新的转移函数 ，定义 终止结点等价类中最长的那个字符串为 ，由上面的性质可以知道，该等价类中的其它字符串都是 的后缀，而显然的，对于 的一些较短的后缀 ，其等价类可能满足 ，因为 不存在的时候， 是可能存在的。
我们定义 为所有满足 中 的最长后缀，则存在 。可以较为抽象地理解为：后缀链接指向的等价类的子集为当前状态。也就是如果 为 的子集，则有 。
link的性质
引理
所有 构成一棵以 为根的树。
这是显然的，因为每一个状态有且仅有一个 ，而 没有。这里我们之后会提及，这棵树就是 的 。为了方便理解，我们可以假定
引理
记录 表示 中最长的字符串的长度， 为最短的，则有：
这个可以结合 的引理 进行理解。
有向无环词图
的图论定义包含两部分，其中一部分形成一棵树，其父子满足后缀关系，另一部分是一个 ，具体来讲就是有向无环词图（），每一个结点都是一个 等价类，而我们将 设为起点，则从 开始的到任意结点连成的字符串都是原串的子串。这很显然，我们就是通过这个定义的 的 。
本质上，我们通过在某一个 所表示的所有子串后添入了一个字符 ，使得其转移到了另外一个 中，这意味着，如果 中存在边 ，则有 。
实现
容易发现，我们需要维护的函数有 和 （转移函数）。
记录以下变量：
参考实现
1
2
3
4
| struct SAM
{ int nxt[26],link,len; }Tr[MAXN<<1];
|
需要注意的是 是在线算法，也就是我们动态读入一个字符串，每次对其一个字符 进行处理，且 之前的所有信息都已经被处理妥当了， 的实现没有后效性。
初始化
创建初始节点 ，规定：
参考实现
1
2
3
4
5
| inline void init()
{
Tr[0].link=-1,Tr[0].len=0;
last=0;
}
|
插入
设当前需要处理的字符为 ，上一个处理的字符对应的结点为 。
为字符 新建一个结点 ，得到：，因为此时 对应的最长字符串为其至 的前缀。
我们从 开始遍历 直到 ，其中如果存在 ，则停止。
- 如果 不存在，则 。
- 如果 存在，记录 ：
- 如果 ，则 。
- 否则，我们复制 ，也就是 结点继承了 的所有信息，并修改 ，同时修改 ，并从 开始遍历后缀链接直到 ，将所有 修改为 。
更新 。
关于克隆步骤的不完全解释
我们找到了 和 ，但 并不是能够容纳加上 后的后缀的等价类，存在 ，相当于我们现在找到了一个全新的等价类，所以需要在 上为其构建新的结点，而其等价类满足上述式子，所以我们的 需要那样连。读者感性理解一下。
参考实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| inline void build(char *s)
{
last=Idx=1;
for(int i=1;s[i];++i)
{
int c=s[i]-'a',cur=++Idx,p=last;
Tr[cur].len=i,Siz[cur]=1;
for(;p&&!Tr[p].nxt[c];p=Tr[p].link) Tr[p].nxt[c]=cur;
if(!p) Tr[cur].link=1;
else
{
int q=Tr[p].nxt[c];
if(Tr[p].len+1==Tr[q].len) Tr[cur].link=q;
else
{
int cl=++Idx;
Tr[cl]=Tr[q];Tr[cl].len=Tr[p].len+1;
for(;p&&Tr[p].nxt[c]==q;p=Tr[p].link) Tr[p].nxt[c]=cl;
Tr[q].link=Tr[cur].link=cl;
}
}
last=cur;
}
}
|
正确性证明
经过前人的不懈努力，我们得到了结论：
的构建时间复杂度为 ；
的存储空间复杂度为 ；
的结点数不会超过 ；
的 数不会超过 。
至于证明，感兴趣的读者可自行查阅。
运用 & 性质
其实 的运用多种多样，我第一次学的时候因为不知道怎么用所有板子打了等于白打，因为只会写 build 函数，所以，我会在例题中详细写出 的各种用法极其使用方法。
这里抛出两个十分有用的性质：
- 每个节点的 等于其子树内所有结点对应的 的集合。也就是我们提及的 构成的 的互相包含性。
- 如果结点 是 的祖先，则结点 对应的字符串是结点 对应的字符串的后缀。
- 每个状态表示的子串个数为 。
例题
查询子串出现次数
题目简介
题目名称：后缀自动机
题目来源：洛谷
评测链接：https://www.luogu.com.cn/problem/P3804
形式化题意：给定一个字符串，求出所有长度大于 的子串出现个数乘以其长度的和。
数据范围：
考虑我们前面提到的性质。在 上，一个字符串出现的次数应当包含其作为某个串的后缀出现时的次数和，也就意味着，我们需要对 做一次子树和才能得到当前结点表示的字符串的出现次数。
需要注意的是，在建 时的克隆结点不算做次数内，初始化为 ， 实际上是 的交集，并不代表任何有效的字符串，因为 存储了的字符串实际上都在 和 中了。
然后乘上长度，直接上每个结点最大的就是了。
AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
|
#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
x=0;
char ch=getchar(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e6+10;
int Len,Idx,last,Siz[MAXN];
ll ans;
char Str[MAXN];
struct SAM
{ int nxt[26],link,len; }Tr[MAXN];
inline void build(char *s)
{
last=Idx=1;
for(int i=1;s[i];++i)
{
int c=s[i]-'a',cur=++Idx,p=last;
Tr[cur].len=i,Siz[cur]=1;
for(;p&&!Tr[p].nxt[c];p=Tr[p].link) Tr[p].nxt[c]=cur;
if(!p) Tr[cur].link=1;
else
{
int q=Tr[p].nxt[c];
if(Tr[p].len+1==Tr[q].len) Tr[cur].link=q;
else
{
int cl=++Idx;
Tr[cl]=Tr[q];Tr[cl].len=Tr[p].len+1;
for(;p&&Tr[p].nxt[c]==q;p=Tr[p].link) Tr[p].nxt[c]=cl;
Tr[q].link=Tr[cur].link=cl;
}
}
last=cur;
}
}
struct G
{
int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
Edge[++Total]=(G){Head[u],v};Head[u]=Total;
}
void dfsTree(int x)
{
for(int e=Head[x],v;e;e=Edge[e].next)
{
dfsTree((v=Edge[e].to));
Siz[x]+=Siz[v];
}
if(Siz[x]!=1) checkMax(ans,(ll)Siz[x]*Tr[x].len);
}
int main()
{
scanf("%s",Str+1);
build(Str);
for(int i=2;i<=Idx;++i) addEdge(Tr[i].link,i);
dfsTree(1);
write(ans);
return 0;
}
|
模板
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| const int MAXN=2e6+10;
int Len,Idx,last;
ll ans;
char Str[MAXN];
struct SAM
{ int nxt[26],link,len; }Tr[MAXN];
inline void build(char *s)
{
last=Idx=1;
for(int i=1;s[i];++i)
{
int c=s[i]-'a',cur=++Idx,p=last;
Tr[cur].len=i;
for(;p&&!Tr[p].nxt[c];p=Tr[p].link) Tr[p].nxt[c]=cur;
if(!p) Tr[cur].link=1;
else
{
int q=Tr[p].nxt[c];
if(Tr[p].len+1==Tr[q].len) Tr[cur].link=q;
else
{
int cl=++Idx;
Tr[cl]=Tr[q];Tr[cl].len=Tr[p].len+1;
for(;p&&Tr[p].nxt[c]==q;p=Tr[p].link) Tr[p].nxt[c]=cl;
Tr[q].link=Tr[cur].link=cl;
}
}
last=cur;
}
}
|