Dai Chao

fordring866@gmail.com | Put your faith in the Light!

LCP数组、后缀自动机、后缀树(?)

LCP数组

定义

有了后缀数组,也就有了每个后缀的大小顺序。

但现在我们有另一个奇怪的需求:

对于任意两个后缀,求它们的最长公共前缀(Longest Common Prefix, LCP)。

啊?为什么有这个需求?我也不知道,但大佬说很有用,那就求吧。

i < j,记LCP(i,j)为suffix(sa[i])suffix(sa[j])的LCP长度。

换句话说,就是把后缀从小到大写出来,第i个和第j个的LCP长度就是LCP(i,j)。

现在假设这个LCP(i,j)的值为8,内容是”fordring”(不失一般性)。

也就是说,第i大和第j大的后缀,都以”fordring”开头。

那岂不是说,夹在它俩之间的后缀,都以”fordring”开头?(毕竟它们是排列好的)

于是我们得到了一条重要的结论(虽然没有严格证明):

LCP(i,j) = min(LCP(k,k+1)), k = i, i+1, ..., j-1

所谓LCP数组(常记为height),其元素height[k]的值就是LCP(k,k+1)。

有了LCP数组后,就可以结合上面的结论,用RMQ(留坑)迅速查询到任意两个后缀的LCP长度了。

思路

先把后缀按照位置顺序写出来,比如assassin, ssassin, sassin, assin, ssin, sin, in, n。

然后,求一个后缀数组sa的反查数组rank。如果说sa[i]是第i小后缀的位置,那么rank[i]就是位置i后缀的名次。

也就是说,sa[rank[i]]就是i,rank[0]就是”0”在sa中的下标。

然后,取assassin,再取刚好比它大的后缀assin,直接比较得到ass,height值为3。

观察两者下家,可以肯定ssassin一定比ssin小。

于是,刚好比ssassin大的那个后缀,一定在(ssasin, ssin)的区间内。

因此,assassin的下家ssassin,它对应的height值至少是3-1=2,那我直接从第3个字符开始比较就稳了!

换句话说,按位置顺序求height值,每次递减不超过1!

复杂度

将字符串比作一列高为N的、从下往上搭建的积木,将N个后缀比作N列积木,于是形成了一个N*N格子的房间。

直接比较字符,意味着顺着积木向上走一步;跳到下一字符串,意味着向右下角走一步(height值递减不超过1)。

想像一个N*N个格子的房间,你从左下角出发,要到达最右一排。不能穿墙,每次只能往或者右下走一步。请问到达最右一排时,你要走多少步?

首先,走到最右时,必定走了N-1个右下步。

其次,为了不穿底,至少要走N-1个上步;为了不穿顶,至多能走2N-2个上步。

因此,复杂度为O(N)。

代码

void height(int *r, int *sa, int n) {
	int i, j, k;
	for (i = 1; i <= n; i++) rank[sa[i]] = i;
	for (i = k = 0; i < n; height[rank[i++]] = k)
		for (k ? k-- : 0, j = sa[rank[i] - 1]; r[i+k]==r[j+k]; k++);
	return;
}

懒得讲了。

后缀自动机

Suffix Automaton, SAM.

这个东西我昨天看了一晚上,确实很强大,但也很抽象。鉴于自己没有理解透彻,就只粘贴一下这篇比较完美的教程(需要知道自动机是什么)。下面说一下文章梗概。

(试着讲讲)关键概念

最关键、最抽象的概念:equivalence class(等价类), suffix link(后缀链)。

据我理解,把字符串str的所有子串的集合称为S,对每个子串定义一个endpos集合,包含了该子串所有出现的结束位置(一个子串可能出现多次)。在S上定义等价关系,两子串等价当且仅当它们的endpos集合相等。于是,S被划分成了若干等价类,每个等价类都对应SAM里的一个状态,同样也对应一个endpos集合。

例如对于abcbcbc,”bc”和”c”的endpos集合都是{2,4,6},因此属于同一状态,但”bcbc”则是{4,6},诸如此类。

接下来,文章论证了每个状态所对应的子串集合,都是形如[i,j],[i+1,j],...,[i+k,j]这样的,例如{“abcc”,”bcc”,”cc”}。

接下来,文章论证了SAM的状态可以通过单个字符来转换,其意义是:假如状态A通过字符c转移到状态B,那么A的最长子串加上c,恰好就是B的最短子串。

后缀链,很抽象却很神奇。文章论证了每个状态的endpos集合,要么交集为空,要么呈真包含关系,而这恰好满足的性质。顺着这种包含关系,就能形成一棵以起始状态为根的树,且SAM里的每个状态都包含于其中。后缀链就是这棵树的有向边。

构造算法的思路

接下来是粘贴过来的构造算法,但我理解不深,无法解释整个算法为什么正确,只好做一些脚注便于大家理解。

len就是每个状态的子串集合中,最长子串的长度;link是该状态的后缀链所指向的状态(编号)。起始状态啥也没有,所以这样赋值,而-1代表树根。

Now the whole task boils down to implementing the process of adding one character c to the end of the current string. Let us describe this process:

旧状态机包含了所有旧字符串的子串,所以新状态cur就要(试图)包含多出来的子串,也就是所有以c结尾的子串,其len值理所当然等于新字符串的长度。

顺着后缀链,如果没有状态接收c,就说明旧串不含c(需证明),所以所有新子串的endpos都只有一个元素——新串末尾的位置。这种情况下,所有路过的状态都应该接受c到达cur(需证明),新子串都属于cur,且cur应该指向树根,插入结束。

如果旧串含c,那就麻烦了,因为新子串可能与旧子串重复,无法立即推断endpos了。

我不懂该怎么解释这种情况下算法的行为,但我猜关键在于后缀链的某些特性。

构造算法的实现

struct state {
	int len, link;
	map<char, int> next;
} st[MAXLEN * 2];

const int MAXLEN = 100000;
int sz, last;

void sa_init() {
	st[0].len = 0;
	st[0].link = -1;
	sz = 1;
	last = 0;
}

void sa_extend(char c) {
	int cur = sz++;
	st[cur].len = st[last].len + 1;
	int p = last;
	while (p != -1 && !st[p].next.count(c)) {
		st[p].next[c] = cur;
		p = st[p].link;
	}
	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].next = st[q].next;
			st[clone].link = st[q].link;
			while (p != -1 && st[p].next[c] == q) {
				st[p].next[c] = clone;
				p = st[p].link;
			}
			st[q].link = st[cur].link = clone;
		}
	}
	last = cur;
}

用途

实在太广了。如你所见,SAM以O(N)的方式涵盖了所有子串的信息,因此可以回答几乎所有关于子串的问题(用解决图论问题的方式)。

嗯……我只是知道可以回答,不知道怎么回答,还需要刷点题才行。听说后缀数组在实战中更好用,某些极端情况下才需要祭出SAM(我肯定是碰不到了)。

后缀树

就是把后缀做成Trie树。

具体用途还不清楚,以后有经验了再更新吧。

后记

字符串问题真尼玛好玩!