后缀数组(SA) 详解

一类解决字符串问题的有力工具。

首先是搞出一个sa数组。其中$sa[i]$表示所有非空后缀中，字典序第$i$大的后缀从哪里开始。
同时也可以处理出来一个rk数组，其中$rk[i]$表示这个后缀排第几。
显然最后有$rk[sa[i]] = sa[rk[i]] = i$.

$\mathcal{O(n^2 log n)}$
直接string + sort.

$\mathcal{O(n log^2 n)}$
考虑倍增维护。

对于每个位置$i$，如果我们知道了$s[i…i+w-1]$的排名，那就可以倍增一下，搞个二元组排序即可。
倍增是log的，排序nlogn，共$\mathcal{O(n log^2 n)}$.

$\mathcal{O(n log n)}$
优化排序，用基数排序即可。
注意细节的优化，不然会挂。

#include <bits/stdc++.h>
#define dbg(x) std::cerr << #x << " = " << x << "\n"
using namespace std;
typedef long long ll;

const int N = 1000000 + 5;
int n, w, m;
int rk[N<<1], num[N], cnt[N], id[N<<1];
char s[N];
bool cmp(int x, int y, int w) {
	return id[x] == id[y] && id[x + w] == id[y + w];
}
int main() {
	scanf("%s", (s + 1)); n = strlen(s + 1);
	m = max(n, 300);
	for(int i = 1; i <= n; i++) rk[i] = s[i], ++cnt[rk[i]];
	for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
	for(int i = n; i >= 1; i--) num[cnt[rk[i]]--] = i;
	for(w = 1; w < n; w <<= 1) {
		memset(cnt, 0, sizeof(cnt));
		int p = 0;
		for(int i = n; i >= n - w + 1; i--) id[++p] = i;
		for(int i = 1; i <= n; i++) if(num[i] > w) id[++p] = num[i] - w;
		for(int i = 1; i <= n; i++) ++cnt[rk[id[i]]];
		for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
		for(int i = n; i >= 1; i--) num[cnt[rk[id[i]]]--] = id[i], id[i] = rk[i];

		m = 0;
		for(int i = 1; i <= n; i++) rk[num[i]] =  cmp(num[i], num[i - 1], w) ? m : ++m;
	}
	for(w = 1; w <= n; w++) printf("%d ", num[w]);
	return 0;
}

# 后缀数组, 字符串

后缀数组(SA) 详解

评论

分类

Your browser is out-of-date!