史上全网最清晰后缀自动机学习(一)基本概念入门

缘起

该拔掉的毒瘤总归得拔掉. SAM（suffix auto mation 后缀自动机）大叔, 来吧！hihocoder 1441 : 后缀自动机一·基本概念

爱了爱了~ hihocoder把后缀自动机做成了一个专题. 一共6道题, 循序渐进. 我打算沿着hihocoder铺好的路前进, 攻克后缀自动机（下面简称SAM）这种强大的字符串处理工具.

分析

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

输入
第一行包含一个字符串S，S长度不超过50。

第二行包含一个整数N，表示询问的数目。(1 <= N <= 10)

以下N行每行包括一个S的子串s，s不为空串。

输出
对于每一个询问s，求出包含s的状态st，输出一行依次包含shortest(st)、longest(st)和endpos(st)。
其中endpos(st)由小到大输出，之间用一个空格分割。

样例输入
aabbabd
5  
b
abbab
aa
aabbab
bb
样例输出
b b 3 4 6  
bab aabbab 6  
aa aa 2  
bab aabbab 6  
bb aabb 4

首先做SAM的一些基本概念的介绍. 不然题目有一些术语读者可能看不懂.

先来一个直观的图示, 对于S="aabbabd", 它的SAM（事实上, 任何字符串都可以构造出相应的SAM）长下面的样子

image

首先, 形象的说, 所谓的自动机就是机器内部有一些状态节点, 然后自动机不断的接收一些文本串字符, 然后根据一些规则, 在自动机的节点之间进行跳转. 站在编译原理的角度来说, SAM本质上是一个DFA. 而DFA 可以使用一个五元组 <字符集，状态集，转移函数、起始状态、终结状态集> 来描述.

所以如果要讲清楚SAM， 起码（因为SAM除了DFA有的这5部分, 还有一个大杀器——后缀link, 这是后话）要研究清楚这5部分分别是什么才行。

字符集

这不多说, 题目一般都是小写英文字母.

状态集

要想讲清楚一个字符串S的SAM的状态集, 就不得不引入一个概念——子串的结束位置集合（endpos）

对于S的子串s, 令endpos(s)=s在S中所有出现的结束位置集合. 举个例子

S="aabbabd", s = "ab" 是S的子串, 然后s在S[3]处、S[6]处结束（索引从1开始，而不是从0开始）. 所以

endpos("ab")={3,6}

类似的

endpos("a") = {1,2,5}
endpos("abba") = {5}

我们把S的所有子串找出来, 记做集合SS， 然后我们在SS上建立等价关系R

R 是SS×SS的子集, (s1,s2)属于R的充要条件是endpos(s1)和endpos(s2)这两个集合相等.

那么我们用R就可以将SS划分为若干个等价类（即SS的子集）. 我们说, SAM的状(节)态(点)就是这些等价类. 还是以S="aabbabd"为例

因为SS被分成了0~9共计10个等价类, 所以S对应的SAM有10个状态（或者说S的SAM有10个节点）.

起始状态

空串所在的等价类（只有它自己在这个等价类中）就是SAM的起始状态. 例如图1中的0号状态节点

终结状态

注意措辞哈, 我们说DFA的起始状态而没有说DFA的起始状态集. 说明DFA的起点只有1个（单入口）. 但是我们说DFA的终结状态集. 说明DFA可以是多出口的. 但是SAM作为DFA, 也只有一个终结状态, 即原串S所在的等价类.

例如图1中的9号状态节点

转移函数

这个对于DFA而言是最为关键的部分——因为它直接决定了自动机是怎么工作的. 而自动机的转移函数就是二元函数

tran(i,j) = k, 其中 i和k都是自动机的状态, j是读入的字符集中的一个字符

形象的讲——自动机的转移函数就是当前自动机处在i节(状)点(态),读入一个字符集中的字符j, 自动机将跳转到节点k, 了解ac自动机的童鞋是很清楚ac自动机的转移函数的——就是通过暴力跳fail获取的。

那么后缀自动机的转移函数长什么样子呢? 其实就是要回答下面的问题

SS的一个等价类i中每个字符串s后面加一个字符j, s变成s', 那么s'将属于哪个等价类? 如果都属于等价类k 的话, 则 tran(i,j) = k

首先等价类i中所有字符串加上这个字符j都会变到同一个等价类里面去。这是显然的. 很容易使用反证法证明. 所以上述转移函数trans的定义是well-defined 的。

下面要讲解的后缀link本题其实用不到, 但是既然本文是讲解SAM的基本属性和概念, 就必须把它讲出来. 而且期间可以理解等价类的结构. 这个结构对于切本题也是很有帮助的.

后缀link

上面的5部分都是DFA有的东西. 而这里的后缀link是SAM特有的东西. 要说清楚后缀link的话, 我们必须引入下面有关的等价类的结构的定理.

等价类结构定理: 假设等价类中包含的所有字符串为{s1,..,sn}, 则s1,...sn的长度两两不同. 假设s1,...,sn 就是按照长度升序排序. 则s_{i+1}长度比si的长度刚好大1. 而且si是s_{i+1}的后缀. 也就是说: 等价类其实是它里面最长的那个元素的一系列连续的后缀构成的集合.

如果此定理成立的话, 则这就意味着s1作为sn的后缀如果再删减一个字符（即如果令s1="x1,...,xk"的话, 删减掉x1）的话, 则变化后的字符串就将属于一个新的等价类（即ss1="x2,..,xk"将属于不同于s1,...,sn所属的等价类）.

则我们就能感觉到随着字符的不断删减（量变）, 删到一定程度，则将跳到别的等价类去（质变）——直至删光所有字符变成空串跳到起点0去.

我们假设i等价类通过上述量变到质变的过程跳到j等价类去了, 则我们就连一条从i到j的弧. 这条弧就称为后缀link.

我们说了, 后缀link是SAM特有的大杀器. 但究竟它为什么是大杀器, 这里按住不表. 后续进阶文章会自然的引入.

言归正传, 为了证明上述定理，我们先证明

引理: 对于S的两个子串s1和s2，不妨设len(s1) <= len(s2)，那么 s1是s2的后缀当且仅当endpos(s1) ⊇ endpos(s2) s1不是s2的后缀当且仅当endpos(s1) ∩ endpos(s2) = ∅。即对于两个子串他们的endpos之间的关系只有包含或交空二择一, 而且分别对应后缀或不是后缀二择一.

证明: 其实是显然的. 如果endpos(s1)和endpos(s2)有交集. 则说明他们在同一个位置结束过, 那等价于就是说明s1是s2的后缀啊~ 所以endpos(s1)一定包含endpos(s2)——因为s2结束过的地方一定有s1 的身影.

有了上面的引理, 我们就知道

等价类结构定理の证明: 因为等价类中每个元素的endpos集合相等, 根据引理, 必是后缀关系. 所以两两长度 不同，如果是后缀关系长度又一样, 那肯定就是相同的元素了呀~ 然后考虑长度最长的那个元素sn和长度最短的那个 元素s1, 根据夹逼的思想, 介于s1和sn之间的任何长度的sn的后缀si的endpos集合都和endpos(s1、sn)相等. 也就是 endpos(si) = endpos(s1) = endpos(sn). 所以定理得证.

我们还有以下推论

推论: 等价类i中的每个元素前面删减一个字符或者后面再接上一个字符都将跑到一个不同于i的等价类中去. 例如 s = "x1,...,xk", 则"x1,...,xkx_{k+1}" 将属于等价类j, 其中j!=i

证明: 假设sn是等价类i中最长的那个元素, 则用反证法（上面已经提过了）很容易证明对于i中任意一个s, s后接上一个字符和sn接上该字符将跳到同一个等价类中去. 而sn接上一个字符之后得到的字符串(记做ssn)的 长度已经严格比sn大了. 所以ssn不可能还属于i, 因为i等价类中最长的元素就是sn. 同理可以证明删减的情况.

进一步的推论: 状态节点沿着后缀link走向0（sam的起点）的有向路径上的弧(都是后缀link, 废话)的起点的 shortest长度=终点的longest的长度+1

进一步推论的证明: 这是上面推论的直接推论.

根据上面的定理和推论，我们不难看出等价类中比较特殊的两个元素是长度最短的那个和长度最长的那个, 分别记做shortest(s)和longest(s)，其中s是等价类中任意一个字符串。为什么这两个元素比较重要呢? **因为 shortest(s) 再删减一个字符或者 longest(s) 再接上一个字符的话, 都将跑到一个不同的等价类中去. 即发生了自动机状态的跳转 **

至此

我相信，我已经将SAM的基本概念全部严格而清晰的讲清楚了. 而且比较自负的认为, 全网应该没有文章能比我这篇文章讲解的SAM更加清楚和严格.

话说完了, 来切代码吧~ 当然, 本题只是概念的入门, 将采用完全暴力的方法求解. 本题的切法要使用上面的等价类结构定理, 不然如果纯暴力其实还不好做呢. 首先就是要找准每个等价类中的sn, 而这个sn可以使用S的所有前缀来找（子串，要么从"前缀的后缀"来看, 要么从"后缀的前缀"来看），然后将这些前缀一个一个的删减前面的字符, 一开始还能在一个等价类中, 可以量变到质变, 就不再在一个等价类里面了. 而且这个等价类显然不会与别的sn产生的等价类一样————等价类结构定理保证的, 因为它不可能是别的sn的后缀。

举个例子吧， 以上面的表格为例. S="aabbabd" 有7个前缀, 分别是

S7="aabbabd"
S6="aabbab"
S5="aabba"
S4="aabb"
S3="aab"
S2="aa"
S1="a"

用每个Sn去产生一族等价类, 例如S6="aabbab"产生3个等价类为状态7、状态8、状态5。这其实就是S6 = aabbab,删除a变成 "abbab", 再删除a变成"bbab", 再删除b变成"bab", 发现一直保持endpos不变. 但是, 再删掉b变成"ab"的时候, 发现endpos真的扩大了，所以"ab"跳到了一个新的等价类去了（即状态8）。然后"ab"再删掉一个字符"a"变成 "b", 则发现endpos又进一步扩大了, 所以"b" 又将跳到一个新的等价类去了（即状态5），如果再删掉"b" 变成空串, 则endpos又将真的扩大了，即跳到SAM的起点0去了. 显然, 随着删减字符, endpos将不减（这是上面的引理保证的）.

//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
//#define LOCAL
const int maxn = 55;
char s[maxn], t[maxn], r[maxn];
int n,endpos[maxn], top;

bool ck(int st, int ed) // 判断s[st,ed]是否会造成endpos变化
{
	int i,j,len, cnt = 0; // cnt是匹配点的个数
	for (i = st, j = 1; i<=ed; i++, j++)
	{
		r[j] = s[i];
	}
	r[j] = 0;
	len = strlen(r+1);
	char *x, *y = s;
	while (x=strstr(y+1, r+1))
	{
		++cnt;
		y = x;
	}
	return cnt ^ top;
}

void kk()
{
	top = 0;
	int len = strlen(t+1), st,ed, tmp;
	char *x, *y = s;
	while (x=strstr(y+1, t+1))
	{
		endpos[top++] = x + len - 1 - s;
		y = x;
	} // 收集endpos
	ed = endpos[top - 1]; // 则 t=s[st,..,ed]
	st = ed - len +1;
	tmp = st;
	while(tmp<=ed)
	{
		if (!ck(tmp, ed))
		{
			++tmp;
		}
		else
		{
			break;
		}
	} // tmp要么>ed要么不满足了
	--tmp;
	for (int i = tmp; i<=ed; i++) // 输出shortest
	{
		putchar(s[i]);
	}
	putchar(' ');
	tmp = st;
	while(tmp)
	{
		if (!ck(tmp, ed))
		{
			--tmp;
		}
		else
		{
			break;
		}
	}
	++tmp;
	for (int i = tmp; i<=ed; i++) // 输出longest
	{
		putchar(s[i]);
	}
	for (int i = 0; i<top; i++) // 输出endpos
	{
		printf(" %d", endpos[i]);
	}
	puts("");
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%s%d",s+1, &n);
	while(n--)
	{
		scanf("%s", t+1);
		kk();
	}
	return 0;
}

ac情况

Accepted

本文的目的是将SAM的基本概念交代清楚. 至于SAM的线性时间构造算法及一系列性质, 将在后续文章给出.