后缀自动机是一种有限状态自动机,它可以(且仅可以)接受一个字符串的所有后缀。
定义
后缀自动机(suffix automaton,以下简称 SAM)的结构包含两部分,有向无环单词图(directed acyclic word graph,以下简称 DAWG)和前缀树(prefix tree)。SAM 中的每个节点都同时存在于这两个结构中。
我们对一个字符串 构造其 SAM,称 是该 SAM 的母串;下文中提到的「子串」、「前缀」与「后缀」,如非特殊说明,均指母串的「子串」、「前缀」与「后缀」。
记 为字符串 的长度。
DAWG
顾名思义,DAWG 是一个 DAG(有向无环图)。
DAWG 中,除起始节点外,每个节点表示一个或多个子串。
节点之间通过转移边相连,每条转移边上有一个字符。
从起始节点沿着转移边走,每条路径都对应着一个子串,即将走过的边上的字符首尾相连得到的子串(显然多条路径会到达同一个节点上)。
我们称在 SAM 上运行一个字符串 ,即为从 DAWG 的起始节点开始,第 次沿着字符 的转移边走,走完 次;如果 是母串的一个后缀,则称到达的节点为可接受的节点。
节点
每个节点所表示的所有字符串,一定是(母串的)某个前缀的若干个长度只相差 的后缀。
例:母串为 ,它的一个前缀为 ,某个节点 所表示的子串可能为 、 和 。
定义节点 中长度最小和最大的子串分别为 和 。
例:母串为 ,它的一个前缀为 ,假设存在某个节点 所表示的子串为 、 和 ,那么 ,。
定义节点 中长度最大的子串在母串中所有出现的结束位置的集合为 。
例:母串为 ,它的一个前缀为 ,假设存在某个节点 所表示的子串为 、 和 ,其中最长的为 ,它在母串中出现过两次,结束位置分别为 和 ,所以 。
性质:任意两个节点的 集合不同。
证明:如果两个节点的 集合相同,则说明这两个节点的出边是等价的(因为它们加上每个字符后得到的那些子串,其结束位置也是分别相同的),可以合并这两个节点。
只有从「表示整个母串的节点」到根的一条路径上的节点的 集合包含母串的末尾,所以只有这些节点是接受节点;并且从起始节点沿着转移边走到这些节点的路径上,将所有转移边上的字符首尾相连,得到的一定是一个后缀(即使它可能在母串的其它位置也出现过多次)。
转移边
到 有一条字符为 的转移边,表示 所表示的所有子串加上一个字符后,得到的子串,都可以由 表示。但不一定 所表示的所有字串都是由 的转移而来。
后缀链接与前缀树
定义 的后缀链接指向 ,当且仅当 且 中的子串均为 子串的后缀,记为 。
例:母串为 ,它的一个前缀为 ,假设存在某个节点 所表示的子串为 、 和 ;另一个节点 所表示的子串为 和 ,则 。
任意节点沿着后缀链接走,最终都会走到 DAWG 的起始节点。以后缀链接为边,所有的节点组成了一棵树,即前缀树。DAWG 的起始节点即为前缀树的根。
性质:前缀树中,子节点的 集合一定是其父节点的真子集,即 。
证明:因为 一定是 的后缀,所以 出现的位置, 一定也出现了,所以 。 如果 ,那么 和 应该被合并为一个点,所以 。
显然,一个节点的 集合包含其所有子节点 集合的并,如果这个节点表示了母串的一个前缀,则加上这个前缀的位置。
构造
在字符集为常数的情况下,SAM 的构造算法时空复杂度均为 ,稍后将证明这一结论。
SAM 的构造是一个增量算法,假设我们已有字符串 的 SAM,只需要考虑如何对其修改得到串 ( 为一个字符)的 SAM 即可。这里将用一个例子来说明这个过程,注意下图中的 和 、 和 、 和 这三组节点在实际情况下均可能是零个或多个节点,为了方便这里画出两个。
设之前表示整个串的节点为 ,从 到起始节点 的路径为 ()。则一定存在一个 ,使得 没有字符 的出转移边,如(黑色边为后缀链接,灰色边为字符 的转移边):
例子中 表示的字符串一定是 所表示字符串的后缀,所以如果 中的字符串添加一个字符后得到的字符串存在于原母串中,则 中的字符串添加一个字符后得到的字符串一定也存在于原母串中。而 中的字符串都是 在前面添加若干个字符得到的,所以 中的子串添加一个字符后得到的字符串可能会不存在于母串中,图中我们假设 是第一个满足「添加一个字符后得到的字符串不存在于母串中」的节点。
现在加入了新的字符 ,所以 添加了字符 后得到的字符串出现了,而且它们是新母串的后缀。我们设这些新的字符串被新节点 所表示,显然 。
注意到,新加入的字符 导致新出现了 (新母串长度)个后缀,这些后缀都需要新的节点来表示。首先,节点 表示了 及更长的后缀,而更短的后缀已经可以由 及其后缀链接的路径上的节点来表示。所以,DAWG 的性质已经被满足。接下来考虑前缀树。
首先,如果不存在这样的 ,满足 有字符 的出边,则需要将 的后缀链接连向起始节点 ,因为新出现的 个后缀都需要节点 来表示,即 ,而为了满足前缀树是一棵树,需要将 的父节点置为树根。
如果 ,即, 中最长的字符串为 中最长的字符串加上字符 后得到的。因为 ,,,所以 ,所以 的后缀链接连向 。
如果 ,此时一定有 ,因为字符串 一定存在于 中,并且存在另一个异于 的节点 ,满足 且 有连向 的转移边。
此时我们不能将 的后缀链接连向 ,因为 中的字符串不全是 的后缀。举个例子, 中有子串 , 中有子串 , 中有子串 , 中有子串 , 中有子串 和 ,因为 不是 的后缀,所以 的后缀链接不能连向 。
我们需要将 拆成两个点,一个点 表示长度小于等于 的子串(例子中的 ),另一个点 表示长度更大的子串(例子中的 )。
原有的 中,仅有长度小于等于 的子串是 与 中的字符串加上一个字符转移而来的,所以 与 的字符 的转移边应该连向 ,而其它子串均为其它节点转移而来的,所以其它节点的转移边应该连向 ,并且 应为原有的 ,并且 ,然后新节点 的后缀链接 。
注意到,在构造的过程中,每个子串都有对应的节点来表示,并且每个节点的 集合不会相同(根据对前缀树结构的改变,容易证明这一结论),所以构造算法是正确的。
实现
实现中要注意的是,节点只需要记录 ,而不需要记录 ,因为 。在将 拆成两个点时,因为要将「其它的点」连向 点,所以直接将原来的 点作为 点,修改其 属性,并新建一个 点,将需要连向 点的连过去即可 —— new 和 old 正是此处命名 与 的用意。
const int CHARSET_SIZE = 26; // 字符集大小为常数
struct SuffixAutomaton
{
struct Node
{
// ch 表示转移边,next 表示后缀链接
Node *ch[CHARSET_SIZE], *next;
int max;
Node(int max = 0) : ch(), next(NULL), max(max) {}
// v->min = v->next->max + 1
int getMin()
{
return next->max + 1;
}
} *start, *last; // start 为起始节点,last 为表示整个母串的节点
// 注意先调用初始化
void init()
{
start = last = new Node;
}
// 加入一个新的字符,将 SAM 扩展
Node *extend(int c)
{
// 节点 u 表示新的整个母串
Node *u = new Node(last->max + 1), *v = last;
// 将 last 的后缀链接路径上没有字符 c 出边的 v 全部连向 u
// 注意判断 v 跳到 NULL 上
for (; v && !v->ch[c]; v = v->next) v->ch[c] = u;
// 如果 v 跳到了 NULL,则需要让 v 的后缀链接指向起始节点(也就是前缀树的根)
if (!v)
{
u->next = start;
}
else if (v->ch[c]->max == v->max + 1)
{
// 直接将 u 的后缀链接连向 v 经过 c 的边转移后的点
u->next = v->ch[c];
}
else
{
// 拆点,n 为新节点,o 为旧节点
Node *n = new Node(v->max + 1), *o = v->ch[c];
// 复制原有节点的出边到新节点 n 的出边
std::copy(o->ch, o->ch + CHARSET_SIZE, n->ch);
// 新节点 n 的后缀链接指向原有节点的后缀链接目标
n->next = o->next;
// 旧节点和新节点 u 的后缀链接指向新节点 n
o->next = u->next = n;
// 将路径上原有转移边指向 o 的节点改为指向 n
for (; v && v->ch[c] == o; v = v->next) v->ch[c] = n;
}
last = u; // 更新「表示整个母串的节点」
return u;
}
};
复杂度证明
接下来我们证明这个算法的时空复杂度,它可以达到线性的空间复杂度,并在字符集为常数的情况下,达到线性的时间复杂度。
空间复杂度
整个结构包含两部分 —— DAWG 和前缀树,我们需要分别证明节点数和 DAWG 的边数是线性的,并且与字符集无关。
首先,每次加入节点时,最多新建两个节点,所以显然节点数的上界是 ,这一部分的复杂度得证。
对于 DAWG 的转移边,我们可以再将其分为两部分 —— 我们以起始节点为根,对 DAWG 建立一棵生成树,树边的数量一定是线性的,接下来只需要考虑非树边的数量。
我们定义集合 表示所有非树边,集合 表示串的所有后缀。如果我们能找到一个映射 ,使得对于任意的 ,若 ,一定有 (即 为单射),即可证明 。
对于两个节点 ,显然只可能存在一条非树边 或 ,假设存在 ,那么我们找到下面三段字符串:
- 从生成树的根沿着树边走到 ,将经过的所有转移边上的字符按顺序首尾相接(因为是沿着树边,所以这个串是唯一的);
- 这条转移边上的字符;
- 从 开始,沿着字符字典序最小的转移边(可以是树边或非树边)走,直到走到一个可接受的节点 ,将经过的所有转移边上的字符按顺序首尾相接。
设这三段拼接得到得到的字符串为 ,因为这三段都是唯一的,所以 是唯一的,记 ;又因为整条路径是从起始节点走到一个可接受的节点,所以 一定是母串的一个后缀,并且,这条非树边 是运行字符串 时经过的第一条非树边。
- 每条非树边 都能对应到一个 ;
- 每个被对应到的 都能对应到唯一一个 。
所以,如果有两条边 和 满足 ,则一定有 —— 所以非树边的数量一定小于等于后缀的数量,即线性。
综上所述,SAM 中的节点数及其 DAWG 上的转移边数均为线性,即 SAM 的空间复杂度为线性,且与字符集大小无关。
时间复杂度
代码中时间复杂度并不显然的地方有以下两处:
Node *u = new Node(last->max + 1), *v = last;
// 将 last 的后缀链接路径上没有字符 c 出边的 v 全部连向 u
for (; v && !v->ch[c]; v = v->next) v->ch[c] = u;
如果 last
等于 start
,则 last->next
为空,此时显然只会经过常数时间;否则,我们关注 last->next->max
这个量的变化:
- 循环一定会执行第一次(
v
一定会被赋值为last->next
),也就是说,循环终止时v->max
最大为last->next->max
,并且,v->max
经过常数时间即可从更大的值变为last->next->max
; - 之后循环每进行一次,都会使
v->max
至少减少 1(因为v->next->max
一定小于v->max
); - 循环结束后,
u->next
被赋值为一个max
为v->max + 1
的节点,而last
被赋值为u
,也就是说,last->next->max
的值变为v->max + 1
。
除每次调用 extend
的第一次循环外,每次循环 v->max
至少减少 ,而循环结束后,在下一次调用 extend
的第一次循环后(不计接下来将要分析的另一个 for
语句,这之间经历了常数时间),v->max
增加了 —— 所以 次调用 extend
后,这条 for
语句的总时间复杂度为 。
下面的另一个 for
:
// 将路径上原有转移边指向 o 的节点改为指向 n
for (; v && v->ch[c] == o; v = v->next) v->ch[c] = n;
我们考虑 o->max
的变化。首先,考虑下图中的这种情况,前三个 v
每个所转移到的节点都不同,这样 o->max
最多比 v3->max
多 ,而其它的情况,如果每个 v
转移到了多个节点,则转移到 o
的节点会离 v3
更远,其 max
会更小,即 o->max
会更小。注意,这里没有要求进入了新建节点 n
的分支,也就是说,即使没有新建节点 n
,这一段也是成立的。
即,每一次 extend
调用后,o->max
最多会增加 ,这种情况下循环只进行第一次。
这条循环语句必第执行一次,之后每执行一次,都会使一个像 v2
这样的节点引出一条连向 n
的转移边,而每多进行一次循环,转移边连向 o
的节点就会少一个,每一次减少的节点都是给 o
贡献了最大的 max
的节点,所以每次 o->max
都会至少减小 —— 所以 次调用 extend
后,这条 for
语句的总时间复杂度也为 。
另外,和字符集相关的语句只有复制出边的这一行:
// 复制原有节点的出边到新节点 n 的出边
std::copy(o->ch, o->ch + CHARSET_SIZE, n->ch);
显然,在字符集大小为常数的情况下,这条语句耗费常数时间。
综上所述,在字符集大小为常数的情况下,该构造算法的总时间复杂度为线性。
大字符集的处理
在字符集较大(如,在 C++ 的 int
范围内)的情况下,我们无法使用一个数组来保存所有字符的出边。比较简便的解决方法是使用 STL 容器 map
—— 建立一个从字符到目标节点的映射。
显然,这样做,构造的时间复杂度不会超过 ( 为字符串长度, 为字符集大小),而空间复杂度不会改变。
struct SuffixAutomaton
{
struct Node
{
std::map<int, Node *> ch; // 用 std::map 保存转移边
Node *next;
int max;
Node(int max = 0) : next(NULL), max(max) {}
} *start, *last;
void init()
{
start = last = new Node;
}
Node *extend(int c)
{
Node *u = new Node(last->max + 1), *v = last;
for (; v && !v->ch[c]; v = v->next) v->ch[c] = u;
if (!v)
{
u->next = start;
}
else if (v->ch[c]->max == v->max + 1)
{
u->next = v->ch[c];
}
else
{
Node *o = v->ch[c], *n = new Node(v->max + 1);
n->ch = o->ch; // 复制出边
n->next = o->next;
o->next = u->next = n;
for (; v && v->ch[c] == o; v = v->next) v->ch[c] = n;
}
last = u;
return u;
}
} sam;
拓扑序
SAM 中的 DAWG 满足一个性质,如果有一条转移边 ,则一定有 。类似的,如果 ,也有 。所以,按照每个节点记录的 max
长度排序,可以同时得到 DAWG 和前缀树的拓扑序。
使用计数排序可以做到线性的时空复杂度。
结束位置集合
我们可以在构造完 SAM 后,求出其拓扑序,然后递推求出每个节点的 集合的大小(一般只需要求出其大小,如果需要确切求出集合的元素,需要使用可持久化数据结构维护)。
struct SuffixAutomaton
{
struct Node
{
Node *ch[CHARSET_SIZE], *next;
int max, posCnt; // posCnt 表示其 end-pos 集合的大小
// 对于一个新的节点,如果它表示了一个新的后缀,则它的 end-pos 集合中多一个位置
// 否则它的 end-pos 集合仅仅是前缀树上所有子节点的 end-pos 集合的并
Node(int max = 0, bool newSuffix = false) : ch(), next(NULL), max(max), posCnt(newSuffix) {}
} *start, *last, _pool[MAXN * 2 + 1], *_curr;
// 为了方便枚举所有节点,我们将节点放在内存池中,_curr 指向当前最后一个节点之后
std::vector<Node *> topo; // 存储拓扑序(按照 max 从小到大排序)
void init()
{
_curr = _pool;
start = last = new (_curr++) Node;
}
Node *extend(int c)
{
// 节点 u 表示了一个新的后缀
Node *u = new (_curr++) Node(last->max + 1, true), *v = last;
for (; v && !v->ch[c]; v = v->next) v->ch[c] = u;
if (!v)
{
u->next = start;
}
else if (v->ch[c]->max == v->max + 1)
{
u->next = v->ch[c];
}
else
{
// 节点 n 并没有表示一个新的后缀,所以它对 pos-end 集合的大小没有贡献
Node *n = new (_curr++) Node(v->max + 1, false), *o = v->ch[c];
std::copy(o->ch, o->ch + CHARSET_SIZE, n->ch);
n->next = o->next;
o->next = u->next = n;
for (; v && v->ch[c] == o; v = v->next) v->ch[c] = n;
}
last = u;
return u;
}
// 拓扑排序
std::vector<Node *> &toposort()
{
static int buc[MAXN * 2 + 1];
int max = 0; // 记录最大值,方便清空 buc 数组
// 普通的计数排序
for (Node *p = _pool; p != _curr; p++)
{
max = std::max(max, p->max);
buc[p->max]++;
}
for (int i = 1; i <= max; i++) buc[i] += buc[i - 1];
topo.resize(_curr - _pool);
for (Node *p = _pool; p != _curr; p++)
{
topo[--buc[p->max]] = p;
}
// 清空 buc 数组以便下一次使用
std::fill(buc, buc + max + 1, 0);
return topo;
}
void calc()
{
toposort();
// 按照拓扑序,从子节点向父节点递推
for (int i = topo.size() - 1; i > 0; i--) // i > 0
{
Node *v = topo[i];
v->next->posCnt += v->posCnt;
}
}
} sam;
如果需要动态维护 ,则需要一种数据结构,支持在有根树上加入一条边、删除一条边、求子树和 —— 将子树和转化为链加、单点查询即可用 Link-Cut Tree 维护。
应用
求本质不同的子串数量
每个节点 表示的子串长度在 范围内,所以对 求和即可。这个过程可以在线维护。
sam.init();
int ans = 0;
for (int i = 1; i <= n; i++)
{
char ch = s[i] - 'a';
SuffixAutomaton::Node *v = sam.extend(ch);
ans += v->max - v->min + 1;
}
求字符串的最小表示
设 为一字符串,()表示将 的前 位剪切并拼接在 的最后得到的字符串,所有 中字典序最小的一个,称为 的最小表示。
求一个字符串 的最小表示,先对 建立 SAM,并从起始节点开始,每次找存在的字符最小的出边向后走,并记录这个字符,走 步后,记录下的字符首位连成的字符串即为 的最小表示。
因为所有的 都是 的子串,并且 SAM 上从起始节点开始沿着转移边走的每一条路径都对应着 的一个子串,所以这个算法是正确的。
求两个字符串的最长公共子串
对一个字符串建立 SAM,记录一个当前匹配的长度 ,和当前节点 ,枚举另一个字符串的每个字符 :
- 如果 有字符 的转移边出边,则使 加一,并使 转移到出边指向的节点上;
- 如果 没有字符 的转移边出边,则使 转移到 ,并且使 等于 ,因为 中的字符串加入字符 后在母串中都不存在了,所以要舍弃一些前缀,而转移到 可以使舍弃的前缀最少,留下的串长度最长,而留下的已匹配的串的长度为 ,这时候继续检查节点 有没有字符 的转移边出边,直到有或者 转移到起始节点。
参考资料
- Suffix Automaton Tutorial,Hunt Zhan
- WC2012 后缀自动机课件,陈立杰
- 2015 年信息学奥林匹克中国国家队论文集 - 后缀自动机及其应用,张天扬
- 震惊!SAM复杂度竟如此显然!,张晴川
- A short guide to suffix automata,quasisphere