本文改编自MAXimal :: algo :: Суффиксный автомат. Построение и применения的Google机翻版(什么玩意儿)

后缀自动机是一个处理字符串相关问题很有用的工具,例如检查一个字符串在另外一个字符串中是否出现过,计算一个字符串中不同子串的数量——它们都可以在线性时间内被解决。

从直观上看,后缀自动机保存着所有子串的信息,对于长度为n的字符串来说,它的后缀自动机只需要的空间,同时构造它的时间复杂度为

后缀自动机的定义

后缀自动机是接受字符串所有后缀的最简确定状态自动机:

  • 后缀自动机是一个有向无环图,点称为状态,边称为状态间的转移
  • 其中一个状态称为初始状态,它是整个图的起点
  • 每个转移都被标上符号,从一个状态出发的所有转移上的符号是互不相同
  • 有些状态标记为终止状态。每条从初始状态出发到达终止状态路径上的符号组合后就是一个合法的后缀
  • 后缀自动机是满足上述条件的最简自动机

后缀自动机性质

后缀自动机保存着所有子串的信息,所以从初始状态出发的任意一条路径都对应着一个子串。我们称这条路径匹配这个子串,或者这个子串匹配这条路径。

对于自动机中的每个状态来说,会有一个或者多个来自初始状态的路径,称为这个状态对应这些路径表示的子串。

后缀自动机例子

初始状态为,终止状态标记上星号。

字符串

t0
t0

字符串

t0
t0
*
*
a
a

字符串

t0
t0
a
a
*
*
a
a
*
*

字符串

b
b
t0
t0
b
b
a
a
*
*

字符串

b
b
t0
t0
b
b
*
*
a
a
a
a
*
*

字符串

b
b
t0
t0
b
b
a
a
b
b
*
*
b
b
*
*

字符串

b
b
t0
t0
b
b
a
a
b
b
b
b
b
b
*
*
*
*
b
b
*
*

后缀自动机构造算法

在介绍算法之前,需要理解一些概念和引理。

结束位置endpos的性质以及和后缀自动机的关系

对于字符串s的任何一个子串t,我们定义为t在s中出现的所有位置的结束位置的集合。

如果两个子串,那么认为是等价的。所以根据,所有的非空子串可以分为多个等价类

在后缀自动机中,等价类对应着一个状态

引理1:两个非空子串u和w(等价当且仅当u只作为w的后缀在字符串中出现。

这是显然的,如果u和w的结束位置相同,那么长度小的u一定是w的后缀。相反地,如果u只作为w的后缀出现,那么它们的一定等价。

引理2:两个非空子串u和w()。它们不想交或者包含:

如果有相同的元素,那么说明u和w结束于某些相同的位置,长度短的u就是w的后缀。由于w每次出现的同时也出现u,因此包含。

引理3:对于一个等价类,将其中的子串按照长度非递增排序。那么每个子串的长度比前一个长度小一,并且是前一个子串的后缀。

如果等价类中只包含一个子串,那么引理显然是成立的。

根据引理1,对于两个等价的子串,一个子串必然是另外一个子串的特有后缀,所以一个等价类中不存在长度相同的串。

我们用w表示等价类中最长的串,用u表示等价类中最短的串。根据引理1,u是w的特有后缀,现在考虑所有长度在之间的w的后缀,考虑它们是不是在等价类中。实际上,这些后缀只会在w出现的时候在字符串s中出现,根据引理1,它们都属于等价类。

后缀链

对于一个状态,一个状态对应着一个等价类,另w作为其中最长的子串,其余的子串都是w的后缀。

w的所有后缀中,一部分在w所在的等价类中,另外一部分位于其他的等价类中。于是定义后缀链连接w所有后缀中位于其他等价类并且长度最长的那个后缀所在的等价类。

包含空串,

引理4:所有后缀链组成一个以为根的树。

对于状态v,指向的状态中的子串长度严格小于状态v中的子串,所以跟随后缀链最终可以到达包含空串的

引理5:如果按照包含关系创建一棵树,那么这棵树的结构是和后缀链树的结构相似的。

按照引理2,两个状态的endpos要么包含要么不相交,所以按照包含关系可以创建一棵树。

对于状态以及,根据后缀链的定义以及引理2:

得证。

例子,字符串的后缀自动机以及后缀链树

a
a
b
b
c
c
c
c
b
b
b
b
bc
bc
c
c
ab
ab
b
b
a
a
b
b
abc
abc
c
c
abcb
abcb
abcbc
abcbc
b
b
bc
bc
ab
ab
a
a
abc
abc
abcb
abcb
abcbc
abcbc

小结

在开始介绍算法之前,来总结一下上面的知识:

  • 所有的子串可以根据被归入到多个等价类中
  • 处理等价类外,后缀自动机还包括一个初始状态
  • 每个状态对应这一个或多个子串,表示最长子串长度,表示最短子串长度
  • 对于每个状态,后缀链指向状态中的最长子串长度为。后缀链组成的树也就是集合的包含关系树
  • 对于每个状态
  • 从任何一个状态开始沿着后缀链走,最终可以到达初始状态。在这个过程中,我们会经过一些不重叠的区间,它们的并集是一个封闭的区间

后缀自动机构造算法

这个算法是在线的,每次在构造好的自动机的基础上增加一个字符。

对于每个状态,需要保存以及转移状态信息。

初始条件下,自动机只包含一个起始状态并且指向-1。所有算法要做的就是给后缀自动机增加一个新的字符c。

  • 我们用来表示当前需要增加一个字符的状态,初始情况下,之后每次增加字符后都会修改。
  • 创建一个新的状态,要求先留着。
  • 接下来进行这样的循环:从状态开始,如果不存在字符c的转移,那么增加一个到达的字符c的转移,然后沿着后缀链继续检查——如果不存在字符串c的转移,那么增加一个转移;如果字符串c的转移已经存在,那么停止循环,将停止时检查的状态记为p。这个时候,会出现两种情况:
    • 如果一直没有遇到存在转移的状态,那么最终我们会到达伪状态-1,只需要让后退出。
    • 如果遇到存在字符c转移的状态,另q为转移到的状态,那么又有了两种情况:
      • 如果,只需要令后退出。
      • 否则,创建一个新的状态,将q的转移也拷贝给clone,令。然后,将状态cur和状态q的后缀链指向clone。最后需要完成的事情就是,遍历p的后缀链上的状态,如果存在指向状态q的字符c转移,那么将这个转移重定向到clone(如果不存在,遍历停止)
  • 在任何一种情况下,最后都需要将last设置为cur。

根据后缀链的定义,last开始的后缀链上的状态就是自动机的所有终止状态。

算法正确性证明

  • 我们称转移连续的如果。如果,这个转移是不连续的。转移是否连续决定了算法具体的处理方法,一个连续转移也成为固定转移,在算法进行过程中不会发生变化,而非连续转移会可能在增加一个字符之后发生改变
  • 为了避免歧义,下面描述自动机增加一个字符c的过程。
  • 算法首先创建一个新的状态,匹配整个字符串
  • 创建完新状态后,从对应这整个字符串s的状态开始,尝试给每个s后缀所在状态添加一个向cur的字符串c转移。如果原来不存在转移,直接添加,如果冲突则需要停下来
  • 最简单的情况:如果最终到达伪状态-1,说明字符c在字符串s中从未出现过。此时,所有的转移都已经添加完毕,剩下的工作就是设置cur的后缀链,一定指向0,因为cur对应着所有的后缀
  • 较复杂的情况,我们遇到了一个已经存在的转移。这意味着,我们遇到了对应的后缀自动机(x是长度为的s的后缀),字符串在之前已经被添加进自动机了。假设之前的自动机被正确构造,那么接下来不再需要添加任何新的转移了。但是,在连接后缀链的时候,需要保证的长度等于。然而,这个条件很可能不成立,这个时候就需要对状态进行“分割”
    • 一种情况是是连续的,满足。在这种情况下,只需要将状态的后缀链指向q。
    • 而第二种情况比较麻烦——转移是不连续的,也就是。说明状态q不但对应着长度长度小于等于的子串,还包含了一些更长的子串,所以就需要将那些更长的子串分离出来。分割的方法是:
      • “拷贝”状态q得到状态使得状态,状态的所有转移也需要拷贝给,因为我们不能改变任何原先经过状态的路径,其中,状态的后缀链为状态原先的后缀链,同时状态的后缀链指向状态
      • 拷贝完成之后,将状态的后缀链指向状态
      • 最后还需要将一些指向状态的转移重新定位到状态。那么哪些转移需要重定向呢?就是那些对应着所有后缀的转移,也就是状态后缀链上每个状态关于字符的转移。

线性复杂度证明

首先,我们认为字母表大小是常数,否则线性的时间复杂度是不成立的。每个状态的转移可以保存在B树结构中,如果假设字符表大小是的话,算法时间复杂度为,空间复杂度为。如果字母表足够小并且空间十分足够的话,可以使用一个大小为的数组保存每个字母对应的转移,只需要时间复杂度和空间复杂度。

因此如果字母表的大小为常数的话,那么添加转移、获取转移都只需要时间复杂度。

为了分析算法的时间复杂度,我们可以将算法分为三个部分:

  • 第一部分——遍历后缀链增加关于字符的转移
  • 第二部分——从状态拷贝出新的状态
  • 第三部分——将转移从状态重定向到状态

第一部分和第二部分的线性时间复杂度是显然的,每个操作都增加一条新的转移(每次增加一个字符至多增加2个状态,每个状态的转移数目是固定的,所有全部的转移数是线性增长)。

第三部分就不是那么明显了。令,随着迭代的进行,长度单调递减,所以作为$s$后缀的起始位置也就单调递增。同时,如果第一次迭代前,的距离为,在迭代结束后,的距离会变成2。

因此每次迭代后,字符串作为后缀的起始位置单调递增,这样的迭代过程不会超过时间复杂度。

注:原文中第三部分的证明似乎太过跳跃,实在无法理解结论是如何得出的,笔者也完全不理解自己翻译的文字。

算法实现

首先,我们需要定义一个数据结构来保存所有转移的信息,如果有必要的话,可以增加一个标志表示结束状态。

#define MAXALP 26
struct state
{
	int len, link, next[MAXALP];
};

后缀自动机可以保存在一个数组中,可以证明,后缀自动机的状态数不会超过

#define MAXLEN 1000001
state st[MAXLEN*2];
int sz, last;

初始化后缀自动机:

void sa_init()
{
	sz = last = 0;
	st[0].len = 0;
	st[0].link = -1;
	++sz;
	memset(st[0].next, -1, sizeof(st[0].next));
}

增量算法:

void sa_extend(char c)
{
	int cur = sz++;
	st[cur].len = st[last].len + 1;
	memset(st[cur].next, -1, sizeof(st[cur].next));
	int p;
	for (p = last; p != -1 && st[p].next[c] == -1; p = st[p].link)
		st[p].next[c] = cur;
	if (p == -1) {
		st[cur].link = 0;
	} else {
		int q = st[p].next[c];
		if (st[p].len + 1 == st[q].len) {
			st[cur].link = q;
		} else {
			int clone = sz++;
			st[clone].len = st[p].len + 1;
			st[clone].link = st[q].link;
			memcpy(st[clone].next, st[q].next, sizeof(st[q].next));
			for (; p != -1 && st[p].next[c] == q; p = st[p].link)
				st[p].next[c] = clone;
			st[q].link = st[cur].link = clone;
		}
	}
	last = cur;
}

后缀自动机的应用

不同子串数量

条件:给定一个字符串,求不同子串的数量

时间复杂度

解法:构造的后缀自动机

由于后缀自动机中每一条从初始状态出发的路径都对应的一个子串,同时后缀自动机是最简的,所以问题也就变成了从初始状态开始不同路径的数量

可以采用动态规划的方法,令为从状态开始的不同路径的数量:

最终的答案是(不包括空串)。

子串出现次数

条件:查询字符串在字符串中的出现次数

时间复杂度:的预处理时间,每次查询代价

解法:构造的后缀自动机

首先需要进行预处理:对于每个状态,用来记录集合大小。实际上,子串对应的状态的集合大小等于子串出现的次数,

处理的方法是:首先将所有不是通过拷贝得到的状态(除了初始状态)的置为1。然后,按照从大到小对各个状态执行:

为什么是这样?所有的非拷贝状态个数为,每个非拷贝状态可以和字符串中的一个位置所对应,所以置,其他状态的意思就是,如果在某个位置出现,那么所有的后缀同样会在这些位置出现。

最后,如果想要找到字符串出现次数,只需要找到字符串对应的状态,而就是出现次数。

注:原文中介绍了后缀自动机很多其他性质和其他应用,本文没有涉及,深入理解建议阅读原文、查阅相关论文。