后缀数组(SA)

并非指数字的后缀，而针对字符串而生的算法。

字符串的后缀指是指从某个位置开始到整个串末尾结束的一个特殊子串。

后缀排序

将所有后缀按照字典序排序，利用计数排序时间+倍增复杂度为\(O(nlogn)\) 。

\(sa[i]:\)排名为\(i\)的后缀的起始位置。

\(rk[i]:\)起始位置为\(i\)的后缀的排名。

\(sa[rk[i]]=rk[sa[i]]=i\)。

\(tot[i]:\)计数排序。

倍增排序示意图：

\(rk\)数组的值在排序过程中可重，但最终不能重复。

\(sa\)数组的值在过程与最终都不能重复。

先求出\(sa\)数组再求\(rk\)数组。

height 数组

\(lcp:\)（最长公共前缀）

height 数组的定义

\(height[i]=lcp(sa[i],sa[i-1])\)，即第 $i $名的后缀与它前一名的后缀的最长公共前缀。

\(height[1]\) 可以视作 \(0\)。

引理

\(height[rk[i]] \ge height[rk[i - 1]] - 1\)

struct SA{
	int rk[N], sa[N], sec[N], rk1[2 * N], tot[N], hei[N], cnt = 0, sz = S;
	void init(){
		for(int i = 1; i <= n; i++) rk[i] = s[i], tot[rk[i]]++;
		for(int i = 1; i <= S; i++) tot[i] += tot[i - 1];
		for(int i = n; i >= 1; i--) sa[tot[rk[i]]--] = i;
	}
	void bucsort(){
		for(int i = 0; i <= sz; i++) tot[i] = 0;
		for(int i = 1; i <= n; i++) tot[rk[i]]++;
		for(int i = 1; i <= sz; i++) tot[i] += tot[i - 1];
		for(int i = n; i >= 1; i--) sa[tot[rk[sec[i]]]--] = sec[i], sec[i] = 0;
	}
	void Sa(){
		init();
		for(int k = 1; k <= n; k <<= 1, cnt = 0){
			for(int i = n - k + 1; i <= n; i++) sec[++cnt] = i;
			for(int i = 1; i <= n; i++)
				if(sa[i] > k) sec[++cnt] = sa[i] - k;
			bucsort();
			for(int i = 1; i <= n; i++) rk1[i] = rk[i];
			sz = rk[sa[1]] = 1;
			for(int i = 2; i <= n; i++){
				if(rk1[sa[i]] == rk1[sa[i - 1]] && rk1[sa[i] + k] == rk1[sa[i - 1] + k]) rk[sa[i]] = sz;
				else rk[sa[i]] = ++sz;
			}
			if(sz == n) break;
		}
	}
	void height(){
		int k = 0;
		for(int i = 1; i <= n; i++){
			if(rk[i] == 1) continue;
			if(k) k--;
			int pos = sa[rk[i] - 1];
			while(pos + k <= n && i + k <= n && s[pos + k] == s[i + k]) k++;
			hei[rk[i]] = k;
		}
	}
}P;