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

定义

后缀自动机(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 的转移边 ):

nil

例子中 \( 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 \) 。

nil

注意到,新加入的字符 \( 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 \) 。

nil

情况三

如果 \( 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 \) 的转移边。

nil

此时我们不能将 \( 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 \) 。

nil

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

nil

原有的 \( 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 \) 的用意。

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 的空间复杂度为线性,且与字符集大小无关。

时间复杂度

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

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

// 将路径上原有转移边指向 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.

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

// 复制原有节点的出边到新节点 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 集合的大小(一般只需要求出其大小,如果需要确切求出集合的元素,需要使用可持久化数据结构维护)。

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 \) 求和即可。这个过程可以在线维护。

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 。