后缀自动机是一个有向无环图,节点为状态,有向边为状态转移边的一种有限状态自动机,它可以且仅可以接受一个字符串的所有后缀,并且状态数和转移数都是最少的。

定义

后缀自动机(suffix automaton,以下简称 SAM)的结构包含两部分,有向无环单词图(directed acyclic word graph,以下简称 DAWG)和前缀树(prefix tree)。 SAM 中的每个节点都同时存在于这两个结构中。

我们对一个字符串 \( S \) 构造其 SAM,称 \( S \) 是该 SAM 的 母串(String) ;下文中提到的「子串(Substring)」、「前缀(Prefix)」与「后缀(Suffix)」,如非特殊说明,均指母串的「子串」、「前缀」与「后缀」。

记 \( | S | \) 为字符串 \( S \) 的长度。

DAWG

顾名思义,DAWG 是一个 DAG(有向无环图)。

DAWG 中,除 起始节点(Start) 外,每个 节点(Node) 表示一个或多个子串。

节点之间通过 转移边(Transfer arc) 相连,每条转移边上有一个 字符(Char)

从起始节点沿着转移边走,每条 路径(Path) 都对应着一个子串,即将走过的边上的字符首尾相连得到的子串(显然多条路径会到达同一个节点上)。

我们称在 SAM 上运行一个字符串 \( S \) ,即为从 DAWG 的起始节点开始,第 \( i \) 次沿着字符 \( S_i \)​​ 的转移边走,走完 \( |S| \) 次;如果 \( S \) 是母串的一个后缀,则称到达的节点为 可接受 的节点。

由于 SAM 是一个自动状态机,所以节点也被称为 状态(State)

节点

  • 每个节点所表示的所有字符串,一定是(母串的)某个前缀的若干个长度以 \( 1 \) 为梯度的后缀。

e.g. 母串为 "lyxyxyxtststst" ,它的一个前缀为 "lyxyxyx" ,某个节点 \( v \) 所表示的子串可能为 "yx" 、 "xyx" 和 "yxyx" 。

  • 定义节点 \( v \) 中长度最小和最大的子串分别为 \( min(v) \) 和 \( max(v) \) 。

e.g. 母串为 "lyxyxyxtststst" ,它的一个前缀为 "lyxyxyx" ,假设存在某个节点 \( v \) 所表示的子串为 "yx" 、 "xyx" 和 "yxyx" ,那么 \( min(v)="yx", max(v)="yxyx" \) 。

  • 定义节点 \( v \) 中长度最大的子串在母串中所有出现的结束位置的集合为 \( endpos(v) \) 。

e.g. 母串为 "lyxyxyxtststst" ,它的一个前缀为 "lyxyxyx" ,假设存在某个节点 \( v \) 所表示的子串为 "yx" 、 "xyx" 和 "yxyx" ,其中最长的为 "yxyx" ,它在母串中出现过两次,结束位置分别为 \( 5 \) 和 \( 7 \) ,所以 \( endpos(v)=\{5,7\} \) 。

性质 :任意两个节点的 endpos 集合不同。

证明 :如果两个节点的 endpos 集合相同,则说明这两个节点的出边是等价的(因为它们加上每个字符后得到的那些子串,其结束位置也是分别相同的),可以合并这两个节点。

转移边

\( u \) 到 \( v \) 有一条字符为 \( c \) 的转移边,表示 \( u \) 所表示的所有子串加上一个字符后,得到的子串,都可以由 \( v \) 表示。 但不一定 \( v \) 所表示的所有字串都是由 \( u \) 的转移而来。

后缀链接与前缀树

  • 定义 \( u \) 的 suffix link 指向 \( v \) ,当且仅当 \( |min(u)|=|max(v)|+1 \) 且 \( v \) 中的子串均为 \( u \) 子串的后缀,记为 \( sufflink(u)=v \) 。

e.g. 母串为 "lyxyxyxtststst" ,它的一个前缀为 "lyxyxyx" ,假设存在某个节点 \( v \) 所表示的子串为 "x"、 "yx" 和 "xyx" ;另一个节点 \( u \) 所表示的子串为 "yxyx" 和 "lyxyx" ,则 \( sufflink(u)=v \) 。

  • 任意节点沿着 suffix link 走,最终都会走到 DAWG 的起始节点。以 suffix link 为边,所有的节点组成了一棵子节点指向父节点的树,即前缀树。DAWG 的起始节点即为前缀树的根。

性质 :前缀树中,子节点的 endpos 集合一定是其父节点的真子集,即 \( endpos(v) \subsetneq endpos(sufflink(v)) \) 。

证明 :因为 \( max(sufflink(v)) \) 一定是 \( max(v) \) 的后缀,所以 \( max(v) \) 出现的位置, \( max(sufflink(v)) \) 一定也出现了,所以 \( endpos(v) \subseteq endpos(sufflink(v)) \) 。

如果 \( endpos(v)=endpos(sufflink(v)) \) ,那么 \( v \) 和 \( sufflink(v) \) 应该被合并为一个点,所以 \( endpos(v) \subsetneq endpos(sufflink(v)) \) 。

显然,一个节点的 endpos 集合包含其所有子节点 endpos 集合的并。

只有从「表示整个母串的节点」(终点)沿着前缀树的边,即 sufflink ,到起始点的一条路径上的节点的 endpos 集合包含母串的末尾,所以只有这些节点是接受节点;并且从起始节点沿着转移边走到这些节点的路径上,将所有转移边上的字符首尾相连,得到的一定是一个后缀,即使它可能在母串的其它位置也出现过多次。

构造

在字符集为常数的情况下,SAM 的构造算法时空复杂度均为 \( O(n) \) ,稍后将证明这一结论。

SAM 的构造是一个增量算法,假设我们已有字符串 \( S \) 的 SAM,只需要考虑如何对其修改得到串 \( S+c \)(\( c \) 为一个字符)的 SAM 即可。

这里将用一个例子来说明这个过程,注意下图中的 \( v_​0 \) 和 \( v_1 \) 、 \( v_​2 \) 和 \( v_​3 \) 、 \( v_​4 \) 和 \( v_5 \) 这三组节点在实际情况下均可能是零个或多个节点,为了方便这里画出两个。

设之前表示整个串的节点为 \( last \) ,从 \( last \) 到起始节点 \( start \) 的路径为 \( p_i = \{ v_1 = last, v_2 = sufflink(last), v_3 = sufflink(sufflink(last)), ..., v_k=start \} \) 。则一定存在一个 \( i \) ,使得 \( v_1 \sim v_i \) 没有字符 \( c \) 的出转移边,如(蓝色边为 suffix link , 黑色边为字符 c 的转移边 ):

例子中 \( v_4 \sim v_6 \) 表示的字符串一定是 \( v_​3 \) 所表示字符串的后缀,所以如果 \( v_​3 \) 中的字符串添加一个字符后得到的字符串存在于原母串中,则 \( v_4 \sim v_6 \) 中的字符串添加一个字符后得到的字符串一定也存在于原母串中。而 \( v_​2 \) 中的字符串都是 \( max(v_​3) \) 在前面添加若干个字符得到的,所以 \( v_​2 \) 中的子串添加一个字符后得到的字符串 不一定存在 于母串中。

现在 \( v_1 \sim v_2 \) 添加新的字符 \( c \) 后出现了新的字符串,而且它们是新母串的后缀。我们设这些新的字符串被新节点 \( u \) 所表示,显然 \( max(u)=max(v​_1)+c,min(u)=min(v_​2)+c \) 。

注意到,新加入的字符 \( c \) 导致新出现了 \( |S|+1 \)(新母串长度)个后缀,这些后缀都需要新的节点来表示。首先,节点 \( u \) 表示了 \( min(u)+c \) 及更长的后缀,而更短的后缀已经可以由 \( d \) 及其 suffix link 的路径上的节点来表示。所以,DAWG 的性质已经被满足。

接下来考虑前缀树。

情况一

如果不存在这样的 \( v_​3 \) ,满足 \( v_​3 \) 有字符 \( c \) 的出边,则需要将 \( u \) 的 suffix link 连向起始节点 start ,因为新出现的 \( |S|+1 \) 个后缀都需要节点 \( u \) 来表示,即 \( |min(u)|=1 \) ,而为了满足前缀树是一棵树,需要将 \( u \) 的父节点置为树根。

情况二

如果 \( max(d)=max(v_​3)+c \) ,即, \( d \) 中最长的字符串为 \( v_​3 \) 中的最长字符串加上字符 \( c \) 后得到的。由于:

\[\begin{cases} |max(d)|=|max(v_​3)|+1 \\ |min(u)|=|min(v_​2)|+1 \\ |min(v_​2)|=|max(v_​3)|+1 \end{cases} \quad \Rightarrow \quad |min(u)|=|max(v_​3)|+1+1=|max(d)|+1 \]

且, \( \forall s_{2} \in v_2, \forall s_{3} \in v_3, \) \( s_{3} \) 为 \( s_{2} \) 的后缀,则 \( s_{3}+c \) 为 \( s_{2}+c \) 的后缀,而 \( s_{3}+c \in d, s_{2}+c \in u \) ,可知 \( d \) 中的子串均为 \( u \) 子串的后缀。

所以 \( u \) 的 suffix link 连向 \( d \) 。

情况三

如果 \( max(d) \neq max(v_​3)+c \) ,此时一定有 \( |max(d)|>|max(v_​3)|+1 \) ,因为字符串 \( max(v_​3)+c \) 一定存在于 \( d \) 中,并且存在另一个异于 \( v_i \) 的节点 \( t \) ,满足 \( sufflink(t)=v_​3 \) 且 \( t \) 有连向 \( d \) 的转移边。

此时我们不能将 \( u \) 的 suffix link 连向 \( d \) ,因为 \( d \) 中的字符串不全是 \( u \) 的后缀。举个例子, \( v_3 \) 中有子串 "lyxtst" , \( v_2 \) 中有子串 "alyxtst" , \( t \) 中有子串 "lllyxtst" , \( u \) 中有子串 "alyxtsts" , \( d \) 中有子串 "lyxtsts" 和 "llyxtsts" ,因为 "llyxtsts" 不是 "alyxtsts" 的后缀,所以 \( u \) 的 suffix link 不能连向 \( d \) 。

我们需要将 \( d \) 拆成两个点,一个点 \( n \) 表示长度小于等于 \( |max(v_​3)|+1 \) 的子串(例子中的 "lyxtsts" ),另一个点 \( o \) 表示长度更大的子串(例子中的 "llyxtsts" )。

原有的 \( d \) 中,仅有长度小于等于 \( |max(v_​3)|+1 \) 的子串是 \( v_​3 \) 与 \( v_​4 \) 中的字符串加上一个字符转移而来的,所以 \( v_​3 \) 与 \( v_​4 \) 的字符 \( c \) 的转移边应该连向 \( n \) ,而其它子串均为其它节点转移而来的,所以其它节点的转移边应该连向 \( o \) ,并且 \( sufflink(n) \) 应为原有的 \( sufflink(d) \) ,并且 \( sufflink(o)=n \) ,然后新节点 \( u \) 的 suffix link \( sufflink(u)=n \)。

注意到,在构造的过程中,每个子串都有对应的节点来表示,并且每个节点的 endpos 集合不会相同(根据对前缀树结构的改变,容易证明这一结论),所以构造算法是正确的。

实现

实现中要注意的是,节点只需要记录 \( max \) ,而不需要记录 \( min \) ,因为 \( min(v)=max(sufflink(v))+1 \) 。在将 \( d \) 拆成两个点时,因为要将「其它的点」连向 \( o \) 点,所以直接将原来的 \( d \) 点作为 \( o \) 点,修改其 \( max \) 属性,并新建一个 \( n \) 点,将需要连向 \( n \) 点的连过去即可 —— new 和 old 正是此处命名 \( n \) 与 \( o \) 的用意。

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
const charsetSize = 26 // 字符集大小为常数

type Node struct {
// arc 表示转移边,sufflink 表示 suffix link
arc [charsetSize]*Node
sufflink *Node
max int
}

// Sufflink suffix link of node
func (n *Node) Sufflink() *Node {
return n.sufflink
}

// Max the length of the longest string in state
func (n *Node) Max() int {
return n.max
}

// Min the length of the shortest string in state
// v.min = v.sufflink.max + 1
func (n *Node) Min() int {
return n.sufflink.max + 1
}

// SuffixAutomaton SAM
type SuffixAutomaton struct {
start *Node
last *Node
// start 为起始节点,last 为表示整个母串的节点
}

// Init SAM
// 注意先调用初始化
func (sam *SuffixAutomaton) Init() {
sam.start = &Node{}
sam.last = sam.start
}


// StartNode get start node
func (sam *SuffixAutomaton) StartNode() *Node {
return sam.start
}

// LastNode get last node
func (sam *SuffixAutomaton) LastNode() *Node {
return sam.last
}

// Extend 加入一个新的字符,将 SAM 扩展
func (sam *SuffixAutomaton) Extend(c int) *Node {
// 节点 u 表示新的整个母串
u, v := &Node{max: sam.last.max + 1}, sam.last

// 将 last 的 suffix link 路径上没有字符 c 出边的 v 全部连向 u
// 注意判断 v 跳到 NULL 上
for ; v != nil && v.arc[c] == nil; v = v.sufflink {
v.arc[c] = u
}

// 如果 v 跳到了 NULL,则需要让 v 的 suffix link 指向起始节点(也就是前缀树的根)
if v == nil {
u.sufflink = sam.start
} else if v.arc[c].max == v.max+1 {
// 直接将 u 的 suffix link 连向 v 经过 c 的边转移后的点
u.sufflink = v.arc[c]
} else {
// 拆点,n 为新节点,o 为旧节点
n, o := &Node{max: v.max + 1}, v.arc[c]
// 复制原有节点的出边到新节点 n 的出边
n.arc = o.arc
// 新节点 n 的 suffix link 指向原有节点的 suffix link 目标
n.sufflink = o.sufflink
// 旧节点和新节点 u 的 suffix link 指向新节点 n
u.sufflink = n
o.sufflink = u.sufflink
// 将路径上原有转移边指向 o 的节点改为指向 n
for ; v != nil && v.arc[c] == nil; v = v.sufflink {
v.arc[c] = n
}
}

// update the last node
sam.last = u
return u
}

复杂度证明

接下来我们证明这个算法的时空复杂度,它可以达到线性的空间复杂度,并在字符集为常数的情况下,达到线性的时间复杂度。

空间复杂度

整个结构包含两部分 —— DAWG 和前缀树,我们需要分别证明节点数和 DAWG 的边数是线性的,并且与字符集无关。

首先,每次加入节点时,最多新建两个节点,所以显然节点数的上界是 \( 2|S| \) ,这一部分的复杂度得证。

对于 DAWG 的转移边,我们可以再将其分为两部分 —— 我们以起始节点为根,对 DAWG 建立一棵生成树,树边的数量一定是线性的,接下来只需要考虑非树边的数量。

我们定义集合 \( E \) 表示所有非树边,集合 \( S \) 表示串的所有后缀。如果我们能找到一个映射 \( f:E \to S \) ,使得对于任意的 \( \forall a,b \in E \) ,若 \( f(a)=f(b) \) ,一定有 \( a=b \)(即 \( f \) 为单射),即可证明 \( |E| \leq |S| \) 。

对于两个节点 \( u,v \) ,显然只可能存在一条非树边 \( u \to v \) 或 \( v \to u \) ,假设存在 \( u \to v \) ,那么我们找到下面三段字符串:

  1. 从生成树的根沿着树边走到 \( u \) ,将经过的所有转移边上的字符按顺序首尾相接(因为是沿着树边,所以这个串是唯一的);
  2. \( u \to v \) 这条转移边上的字符;
  3. 从 \( v \) 开始,沿着字符字典序最小的转移边(可以是树边或非树边)走,直到走到一个可接受的节点 \( w \) ,将经过的所有转移边上的字符按顺序首尾相接。

设这三段拼接得到得到的字符串为 \( s \) ,因为这三段都是唯一的,所以 \( s \) 是唯一的,记 \( f(u \to v)=s \) ;又因为整条路径是从起始节点走到一个可接受的节点,所以 \( s \) 一定是母串的一个后缀,并且,这条非树边 \( u \to v \) 是运行字符串 \( s \) 时经过的第一条非树边。

  • 每条非树边 \( u \to v \) 都能对应到一个 \( s \) ;
  • 每个被对应到的 \( s \) 都能对应到唯一一个 \( u \to v \) 。

所以,如果有两条边 \( u \to v \) 和 \( u' \to v' \) 满足 \( f(u \to v)=f(u' \to v')=s \) ,则一定有 \( (u \to v)=(u' \to v') \) —— 所以非树边的数量一定小于等于后缀的数量,即线性。

综上所述,SAM 中的节点数及其 DAWG 上的转移边数均为线性,即 SAM 的空间复杂度为线性,且与字符集大小无关。

时间复杂度

代码中时间复杂度并不显然的地方有以下两处:

1
2
3
4
5
6
7
u, v := &Node{max: sam.last.max + 1}, sam.last

// 将 last 的 suffix link 路径上没有字符 c 出边的 v 全部连向 u
// 注意判断 v 跳到 NULL 上
for ; v != nil && v.arc[c] == nil; v = v.sufflink {
v.arc[c] = u
}

如果 last 等于 start ,则 last.sufflink 为空,此时显然只会经过常数时间;否则,我们关注 last.sufflink.max 这个量的变化:

  • 循环一定会执行第一次( v 一定会被赋值为 last.sufflink ),也就是说,循环终止时 v.max 最大为 last.sufflink.max ,并且, v.max 经过常数时间即可从更大的值变为 last.sufflink.max
  • 之后 循环每进行一次 ,都会使 v.max 至少减少 1 (因为 v.sufflink.max 一定小于 v.max );
  • 循环结束后, u.sufflink 被赋值为一个 maxv.max + 1 的节点,而 last 被赋值为 u也就是说last.sufflink.max 的值变为 v.max + 1

除每次调用 extend 的第一次循环外,每次循环 v.max 至少减少 1,而循环结束后,在下一次调用 extend 的第一次循环后(不计接下来将要分析的另一个 for 语句,这之间经历了常数时间), v.max 增加了 1 —— 所以 \( n \) 次调用 extend 后,这条 for 语句的总时间复杂度为 \( O(n) \); 。

下面的另一个 for

1
2
3
4
// 将路径上原有转移边指向 o 的节点改为指向 n
for ; v != nil && v.arc[c] == nil; v = v.sufflink {
v.arc[c] = n
}

这条 for 语句的总时间复杂度也为 \( O(n) \) ,具体请看原论文 The smallest automation recognizing the subwords of a text第15页Lemma 2.5.

另外,和字符集相关的语句只有复制出边的这一行:

1
2
// 复制原有节点的出边到新节点 n 的出边
n.arc = o.arc

显然,在字符集大小为常数的情况下,这条语句耗费常数时间。

综上所述,在字符集大小为常数的情况下,该构造算法的总时间复杂度为线性。

大字符集的处理

在字符集较大的情况下,我们无法使用一个数组来保存所有字符的出边。最简单的解决方法就是将 arc 改为 map[rune]*Node

显然,这样做,构造的时间复杂度不会超过 \( O(n \log min\{n,\Sigma\})\) ( \( n \) 为字符串长度, \( \Sigma \) 为字符集大小),而空间复杂度不会改变。

拓扑序

SAM 中的 DAWG 满足一个性质,如果有一条转移边 \( u \to v \) ,则一定有 \( |max(u)|<|max(v)| \)="" 。类似的,如果="" \(="" sufflink(v)="u" ,也有="" |max(u)|<|max(v)|="" 。所以,按照每个节点记录的="" max 长度排序,可以同时得到 DAWG 和前缀树的拓扑序。

使用计数排序可以做到线性的时空复杂度。

结束位置集合

我们可以在构造完 SAM 后,求出其拓扑序,然后递推求出每个节点的 endpos 集合的大小(一般只需要求出其大小,如果需要确切求出集合的元素,需要使用可持久化数据结构维护)。

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
type Node struct {
// arc 表示转移边,sufflink 表示 suffix link
arc [charsetSize]*Node
sufflink *Node
max int
// posCnt 表示其 endpos 集合的大小
posCnt int
}

// Sufflink suffix link of node
func (n *Node) Sufflink() *Node {
return n.sufflink
}

// Max the length of the longest string in state
func (n *Node) Max() int {
return n.max
}

// Min the length of the shortest string in state
// v.min = v.sufflink.max + 1
func (n *Node) Min() int {
return n.sufflink.max + 1
}

// PosCnt the size of endpos(n)
func (n *Node) PosCnt() int {
return n.posCnt
}

// SAWithTopo SAM
type SAWithTopo struct {
start *Node
last *Node

// 为了方便枚举所有节点,我们将节点放在内存池pool中,curr 指向当前最后一个节点之后
curr int
pool []Node
strSize int

topo []*Node // 存储拓扑序(按照 max 从小到大排序)
}

// Init SAM
// 注意先调用初始化
func (sam *SAWithTopo) Init(strSize int) {
sam.pool = make([]Node, 2*sam.strSize+1)
sam.strSize = strSize
sam.curr = 0
sam.start = sam.newNode(sam.curr, 0, false)
sam.last = sam.start
sam.curr++
}

// StartNode get start node
func (sam *SAWithTopo) StartNode() *Node {
return sam.start
}

// LastNode get last node
func (sam *SAWithTopo) LastNode() *Node {
return sam.last
}

// newNode 对于一个新的节点,如果它表示了一个新的后缀,则它的 endpos 集合中多一个位置
// 否则它的 endpos 集合仅仅是前缀树上所有子节点的 endpos 集合的并
func (sam *SAWithTopo) newNode(pos int, max int, newSuffix bool) *Node {
n := &sam.pool[pos]
n.max = max
if newSuffix {
n.posCnt = 1
}

return n
}

// Extend add a new char to extend the sam
func (sam *SAWithTopo) Extend(c int) *Node {
// 节点 u 表示了一个新的后缀
u, v := sam.newNode(sam.curr, sam.last.max+1, true), sam.last
sam.curr++

for ; v != nil && v.arc[c] == nil; v = v.sufflink {
v.arc[c] = u
}

if v == nil {
u.sufflink = sam.start
} else if v.arc[c].max == v.max+1 {
u.sufflink = v.arc[c]
} else {
// 节点 n 并没有表示一个新的后缀,所以它对 pos-end 集合的大小没有贡献
n, o := sam.newNode(sam.curr, sam.last.max+1, false), v.arc[c]
sam.curr++
n.arc = o.arc
n.sufflink = o.sufflink
u.sufflink = n
o.sufflink = u.sufflink

for ; v != nil && v.arc[c] == nil; v = v.sufflink {
v.arc[c] = n
}
}

sam.last = u
return u
}

// Toposort 拓扑排序
func (sam *SAWithTopo) Toposort() []*Node {
buc := make([]int, sam.strSize)

max := 0 // 记录最大值,方便清空 buc 数组

// 普通的计数排序
for i := range sam.pool[:sam.curr] {
v := &sam.pool[i]
if max < v.max {
max = v.max
}
buc[v.max]++
}
for i := 1; i <= max; i++ {
buc[i] += buc[i-1]
}

if len(sam.topo) != sam.curr {
sam.topo = make([]*Node, sam.curr)
}
for i := range sam.pool[:sam.curr] {
v := &sam.pool[i]
buc[v.max]--
sam.topo[buc[v.max]] = v
}

return sam.topo
}

func (sam *SAWithTopo) Calc() {
sam.Toposort()

// 按照拓扑序,从子节点向父节点递推
for i := len(sam.topo) - 1; i > 0; i-- {
v := sam.topo[i]
v.sufflink.posCnt += v.posCnt
}
}

如果需要动态维护 \( |endpos| \) ,则需要一种数据结构,支持在有根树上加入一条边、删除一条边、求子树和 —— 将子树和转化为链加、单点查询即可用 Link-Cut Tree 维护。

应用

后缀自动机的强大之处在于能够灵活处理各种子串问题,而且它有两个形态,作为自动机它是一个 DAWG ,而其背后又隐藏着一棵前缀树,可以在这两个特殊的图结构上大做文章.

解决问题时有时需要回到上面分析的各种性质中去思考.

求本质不同的子串数量

每个节点 \( u \) 表示的子串长度在 \( [|min(u)|,|max(u)|] \) 范围内,所以对 \( max(u)−min(u)+1 \) 求和即可。这个过程可以在线维护。

1
2
3
4
5
6
7
sam.Init()
ans := 0
for i := 1;i<=n;i++ {
ch = s[i] - []byte('a')
v := sam.Extend(ch)
ans += v.Max() - v.Min() + 1
}

求字符串的最小表示

设 \( S \) 为一字符串, \( S_i( i∈[0,|S|) ) \) 表示将 \( S \) 的前 \( i \) 位剪切并拼接在 \( S \) 的最后得到的字符串,所有 \( S_i \) 中字典序最小的一个,称为 \( S \) 的 最小表示

求一个字符串 \( S \) 的最小表示,先对 \( S+S \) 建立 SAM,并从起始节点开始,每次找存在的字符最小的出边向后走,并记录这个字符,走 \( |S| \) 步后,记录下的字符首位连成的字符串即为 \( S \) 的最小表示。

因为所有的 \( S_i \) 都是 \( S+S \) 的子串,并且 SAM 上从起始节点开始沿着转移边走的每一条路径都对应着 \( S+S \) 的一个子串,所以这个算法是正确的。

求两个字符串的最长公共子串

对一个字符串建立 SAM,记录一个当前匹配的长度 \( L \) ,和当前节点 \( v \) ,枚举另一个字符串的每个字符 \( c \) :

  • 如果 \( v \) 有字符 \( c \) 的转移边出边,则使 \( L \) 加一,并使 \( v \) 转移到出边指向的节点上;
  • 如果 \( v \) 没有字符 \( c \) 的转移边出边,则使 \( v \) 转移到 \( sufflink(v) \) ,并且使 \( L \) 等于 \( max(sufflink(v)) \) ,因为 \( v \) 中的字符串加入字符 \( c \) 后在母串中都不存在了,所以要舍弃一些前缀,而转移到 \( sufflink(v) \) 可以使舍弃的前缀最少,留下的串长度最长,而留下的已匹配的串的长度为 \( max(sufflink(v)) \) ,这时候继续检查节点 \( v \) 有没有字符 \( c \) 的转移边出边,直到有或者 \( v \) 转移到起始节点。

\( n \) 个串的最长公共子串。求 \( n−1 \) 次两个字符串的最长公共子串即可,\( s_{1,2,3...} = lcs(S_1, lcs(S_2, lcs(S_3, ...))) \) 。

其他

  • 列出模式串在文本串中所有匹配位置(all occurrences)。
  • 求出最长的出现至少 \( k \) 次的子串。寻找最深的节点 \( x \) 满足 \( cnt(x)>=k \) ,其深度即为答案。

相关数据结构

Factor automaton

Suffix automaton 有个类似的数据结构,称作 factor automaton ,它识别一个字串的所有子串,可以看作识别所有子串的 minimal DAWG 。

求出 \( S \) 的 suffix automaton 后,把所有状态标记为 accept state 后就得到了识别所有子串的 DAWG ,但可能不是最简的,做 minimize 即可得到 factor automaton ,而 acyclic DFA 可以用 Revuz’s algorithm 在 \( O(|V|+|E|+|CharSet|) \) 时间内求最简表示。

反过来,可以通过 factor automaton 获得 suffix automaton 。参见 Maxime Crochemore 、 Christophe Hancart 的《 Automata for Matching Patterns 》中的 FA-to-SA 。

Suffix oracle和factor oracle

Suffix oracle 是一种简化的 suffix automaton 。

某次添加字符 \( a \) 时,在 suffix automaton 中可能会进行状态分裂,而 factor oracle 不分裂,相当于把两个状态合并了。

Suffix oracle 可以看作是 suffix automaton 合并了一些状态后得到的自动机。其接受的串的集合是 suffix automaton 接受的串的集合的超集,也就是说它不会遗漏 suffix automaton 接受的串,但可能会有误判。

Suffox oracle 的优点是节点数为 n+1 ,比最坏情况下的 suffix automaton 大致少一半。边数为 \( n \) 到 \( 2n−1 \) 。把 suffix oracle 的所有状态标记为可接受即得到 factor oracle ,且已是最简形态,无法 minimize 。