后缀数组（SA）

目标

将给定字符串 s 的所有后缀排序。

做法 1

sort+暴力匹配判断，复杂度

O(n^2logn)

做法 2

sort+二分哈希判断，复杂度

O(nlog^2n)

，但带着 hash 的大常数。

做法 3（后缀数组）

不会 DC3。只能用倍增求了。

定义 rk[i] 表示以位置 i 开始的后缀（s[i~n]），排完序后，排第几名。定义 sa[i] 表示排完序后，排名为 i 的后缀在原串中的开始位置是 sa[i]。因此不难有 sa[rk[i]] = i。

定义 height[i] 表示排名为 i 和排名为 i-1 的两个后缀的 LCP。

rk 数组的具体求法

倍增法。先把只考虑一个字符的排好序。设当前已经排好了长度为 len 的所有子串，尝试根据二元组 {rk[i], rk[i+len]} 来将所有长度为 2*len 的子串排序（其实就是先比前半段，再比后半段）。具体排序的时候需要用基数排序才能做到 O(n)。

sa 数组的具体求法

根据等式 sa[rk[i]] = i 即可。

height 数组的具体求法

很显然可以万能二分+hash 做到

O(nlogn)

。但是能不能

O(n)

呢？

引理：当 i > 1 且 rk[i] > 1 时，有 height[rk[i]] >= height[rk[i-1]]-1。

证明见 oi-wiki

根据这个东西，我们只要按照 rk 的顺序来求 height，不难发现均摊是 O(n) 的。

code：

CPP

const int N = 1000010;

int n, rk[N], sa[N], height[N], cnt[N];
// rk[i] 表示以位置i开始的后缀 排完序后 排第几名
// sa[i] 表示排完序后 排名为i的后缀在原串中的开始位置是sa[i]
// height[i] 表示排名为i和排名为i-1的两个后缀的LCP
char s[N];
struct node {
	int r[2], pos;
} z[N], zp[N];

void count_sort(int n, int m) { // 基数排序 O(n)
	G(j, 1, 0) {
		memset(cnt, 0, sizeof cnt);
		F(i, 1, n) cnt[z[i].r[j]]++;
		F(i, 1, m) cnt[i] += cnt[i-1];
		G(i, n, 1) zp[cnt[z[i].r[j]]--] = z[i];
		F(i, 1, n) z[i] = zp[i];
	}
	int tot = 0;
	rk[z[1].pos] = ++tot;
	F(i, 2, n) {
		if (z[i].r[0] == z[i-1].r[0] && z[i].r[1] == z[i-1].r[1]) rk[z[i].pos] = tot;
		else rk[z[i].pos] = ++tot;
	}
}

void get_sa(int n) {
	F(i, 1, n) z[i] = {{s[i], 0}, i};
	count_sort(n, 200); // 仅考虑第一个字符的排序
	for (int len = 1; len < n; len <<= 1) { // 当前已经处理好了所有长度为 len 的字符串
		F(i, 1, n) z[i] = {{rk[i], (i+len<=n?rk[i+len]:0)}, i}; // 算出长度为 2*len 的字符串的二元组
		count_sort(n, n);
	}
	F(i, 1, n) sa[rk[i]] = i;
}

void get_height(int n) {
	int k = 0;
	F(i, 1, n) {
		if (rk[i] == 1) continue;
		if (k) k--;
		int j = sa[rk[i]-1];
		while (i+k <= n && j+k <= n && s[i+k] == s[j+k]) k++;
		height[rk[i]] = k;
	}
}

void mymain() {
	scanf("%s", s+1);
	n = strlen(s+1);
	get_sa(n);
	get_height(n);
	F(i, 1, n) {
		printf("%d ", sa[i]);
	}
	puts("");
}

文章操作

目标