2018-01-10

后缀数组 ( SuffixArray )

后缀数组的学习

关于后缀数组

入门解决一些字符串问题的手段
必须要学
主要核心在于两个数组：Height，SA

几个概念

若无特殊说明，定义后缀比较大小为字典序大小
定义：

SA[i]:第 $i$ 小的后缀的下标(即起始位置)。
Rank[i]:第 $i$ 个后缀的排名，与SA互逆。
Height[i]:排名为 $i$ 的后缀与排名为 $i-1$ 的后缀的公共前缀

求解这三个数组是关键，这里采用倍增的思想解决

核心思路

利用后缀之间的关系：

在原字符串中，任意两个相邻的后缀仅有一个字符不同(缺失)

一开始我们会根据每个后缀的第一个字符(视作向后延伸一个长度)进行排序，对应就是遍历所有节点。
n个遍历位置对应n个后缀。我们可以区分一些后缀的大小关系，当然也不是全部。
很显然，只要我们没有比较出所有的大小关系，那么以每个节点向后的长度就要不断增加。靠后的节点位置是没有现成的字符我们对其补零(即默认关键子最优)。
那么我们以 $i (1 <= i <= n)$ 为起点每次向后延伸 $2^k$ 直到排序完毕，整个过程的复杂度就是 $nlogn$。

排序的过程

采用基数排序，复杂度 $O(n)$。
很显然，第 $i$ 次排序排的长度是 $2^{i-1}$。
那么第 $i$ 次排序的每一个对象，根据上一次排序得到的结果可以分成两长度相等的段。显然每个段经过上一次排序后有自己的排名(每个长度也可以对应一个排名，只是一个数字)。现在我们只要对每一组的两个段经行双关键字排序即可。
注意对字符子串排序等价于对上次的排名进行排序。

具体实现有很多细节地方，如果不理解了解大致思想，然后背板子(hua|Ji)

模板

#include <bits/stdc++.h>
const int maxn = 1e6 + 10;
const int inf  = 1e9 + 10;
char s[maxn];
namespace SuffixArray {
	int Rank[maxn], SA[maxn], tmp[maxn], tax[maxn], str[maxn], Height[maxn];
	inline void init(int n){
		for(int i = 1; i <= n; i++)str[i] = int(s[i - 1]);
	}
	bool rsort(int n,int m) {
		memset(tax, 0, sizeof(int)*(m+1));
		for (int i = 1; i <= n; i++)tax[Rank[i]]++;
		for (int i = 1; i <= m; i++)tax[i] += tax[i - 1];
		for (int i = n; i; i--)SA[tax[Rank[tmp[i]]]--] = tmp[i];
	}
	bool cmp(int *f,int x,int y,int w,int n) {
		return f[x] == f[y] && ((x + w > n ? -1 : f[x + w]) == (y + w > n ? -1 : f[y + w]));
	}
	void build(int n) {
		init(n);
		for(int i = 1 ; i <= n; i++) Rank[i] = str[i], tmp[i] = i;
		int m = 1100;
		rsort(n, m);
		for (int p = 1, w = 1; p < n; m = p, w <<= 1) {
			p=0;
			for (int i = n - w + 1; i <= n; i++) tmp[++p] = i;
			for (int i = 1; i <= n; i++)if(SA[i] > w) tmp[++p] = SA[i] - w;
			rsort(n, m);
			for (int i = 1; i <= n; i++) tmp[i] = Rank[i];
			Rank[SA[1]] = p = 1;
			for (int i = 2; i <= n; i++) Rank[SA[i]] = cmp(tmp, SA[i], SA[i-1], w, n) ? p : ++p;
		}
		for (int i = 1, k = 0; i <= n; Height[Rank[i++]] = k) {
			if(k>0)k--;
			int j = SA[Rank[i] - 1];
			for (; str[j + k] == str[i + k]; k++);
		}
	}
} using namespace SuffixArray;

最后是一个小小的证明

即在递推Height数组时，对于如何线性递推有些难以理解。
实际上，本质应该是选择了最有利最合理的递推顺序。
记 $H[i] = Height [Rank[i]]$。则有 $H[i] >= H[i]-1$。
如果上面这个性质是对的，那我们可以按照$ H[1]、H[2]……H[Len]$ 的顺序进行计算，那么复杂度就降为 $O(N)$ 了
让我们尝试一下证明这个性质 : 设 $Suffix[k]$ 是排在 $Suffix[i - 1] $ 前一名的后缀，则它们的最长公共前缀是 $H[i - 1]$ 。都去掉第一个字符，就变成 $Suffix[k + 1]$ 和 $Suffix[i]$ 。如果 $H[i - 1] = 0$或$1$,那么 $H[i] ≥ 0$ 显然成立。否则， $H[i] ≥ H[i - 1] - 1 $(去掉了原来的第一个,其他前缀一样相等)，所以Suffix[i]和在它前一名的后缀的最长公共前缀至少是$H[i - 1] - 1$。