后缀数组从入门到精通

1. 约定

suffix(i)：以i为开头的后缀；

LCP 最长公共前缀 longest common prefix

2. 数组定义

sa[i]: 排名i的后缀的开始下标

rank[i]: 开始下标为i的后缀中名次。

也就是说，sa[rank[i]]=i，rank[sa[i]]=i。

height[i]: LCP(suffix(sa[i]), suffix(sa[i-1]))

通俗的来说，排第i名的和排第i-1名的LCP。

h[i] = height[rank[i]]

也就是说，suffix(i)和比他前一名的后缀的LCP。

3. sa[]数组的求法——倍增$O(nlog_{2}n)$。

对于长度为$2^p$的后缀，我们将$i$和$i+2^{p-1}$组合，用基数排序即可获得新sa值。

如果用sort，复杂度变成$O(nlog_{2}^{2}n)$

4. rank[]的求法——性质$O(n)$

根据rank[sa[i]]=i，可以求出rank[]

5. height[]的求法——h[]数组的性质

根据论文证明，$h[i] \geq h[i-1]-1$，然后我们即可$O(n)$求出height[]

6. 经典题目：

(1) 后缀的LCP问题

很明显，

LCP(suffix(i),suffix(j))=min{height[rank[i+1],rank[i+2],...,rank[j]}

用RMQ即可搞定。

(2) 可重叠最长重复子串

求height的最大值即可。

(3) 不可重叠的最长重复子串

二分长度l，对后缀分组后查询距离即可。

(4) 不可重叠的最长k重复子串

同(3)，加判断要大等k即可。

(5) 不相同的子串个数

子串一定是prefix(suffix(i))，那么如果按照sa[1],...sa[n]插入，每插入一个，贡献(n-sa[i]+1-height[i])个子串，累加即可。

(6) 最长回文子串

复制一遍放在后面然后就是一个LCP。

具体可以看lhq的论文噢~

【BZOJ 1031 JSOI2007 字符加密】

把字符串复制两遍后搞rank值即可。

# include <stdio.h>
# include <string.h>
using namespace std;

const int M=600010;
int p[M],cnt[M],rank[M],rank_t[M],sa[M],sa_t[M],rank_t2[M],s[M],t[M];
char str[M];


inline bool cmp(int *s, int a, int b, int l) {
	return s[a]==s[b] && s[a+l]==s[b+l];
}

void getsa(int n,int m) {
	memset(cnt, 0, sizeof(cnt));
	for (int i=0; i<n; ++i) ++cnt[rank_t[i] = s[i]];
	for (int i=1; i<m; ++i) cnt[i] += cnt[i-1];
	for (int i=n-1; i>=0; --i) sa[--cnt[s[i]]] = i;
	for (int j=1, p=1; p<n; j<<=1, m=p) {
		p=0;
		for (int i=n-j; i<n; ++i) sa_t[p++]=i;
		for (int i=0; i<n; ++i) if(sa[i] >= j) sa_t[p++] = sa[i]-j;
		memset(cnt, 0, sizeof(cnt));
		for (int i=0; i<n; ++i) ++cnt[rank_t2[i] = rank_t[sa_t[i]]];
		for (int i=1; i<m; ++i) cnt[i] += cnt[i-1];
		for (int i=n-1; i>=0; --i) sa[--cnt[rank_t2[i]]] = sa_t[i], t[i] = rank_t[i];
		rank_t[sa[0]] = 0;
		p=1;
		for (int i=1; i<n; ++i) 
			rank_t[sa[i]] = cmp(t, sa[i], sa[i-1], j) ? p-1 : p++;
	}
}

int main() {
	scanf("%s",str);
	int n = strlen(str);
	for (int i=0; i<n; ++i) s[i]=s[i+n]=str[i];
	s[n+n-1] = 0;
	getsa(n*2, 300);
	for (int i=0; i<n*2; ++i) rank[sa[i]] = i;
	for (int i=0; i<n; ++i) p[rank[i]]=s[i+n-1];
	for (int i=0; i<n*2; ++i) 
		if(p[i]) 
			printf("%c", (char)p[i]);
	return 0;
}

【BZOJ 2251 外星联络】

求出h的值后，我们就可以搞出答案啦~

当然这题更快的是用trie。

# include <stdio.h>
# include <string.h>
using namespace std;

const int M=600010;
int sa[M],sa_t[M],rank[M],rank_t[M],rank_t2[M];
int cnt[M],s[M],t[M],h[M],n,ans[M],ansn=0;
char str[M];

inline bool cmp(int *s,int a,int b,int l) {
	return s[a]==s[b] && s[a+l] == s[b+l];
}

inline bool getsa(int n,int m) {
	memset(cnt, 0, sizeof(cnt));
	for (int i=0; i<n; ++i) ++cnt[rank_t[i] = s[i]];
	for (int i=1; i<m; ++i) cnt[i] += cnt[i-1];
	for (int i=n-1; i>=0; --i) sa[--cnt[s[i]]] = i;
	for (int j=1, p=1; p<n; j<<=1, m=p) {
		p=0;
		for (int i=n-j; i<n; ++i) sa_t[p++] = i;
		for (int i=0; i<n; ++i) if(sa[i] >= j) sa_t[p++] = sa[i] - j;
		memset(cnt, 0, sizeof(cnt));
		for (int i=0; i<n; ++i) ++cnt[rank_t2[i] = rank_t[sa_t[i]]];
		for (int i=1; i<m; ++i) cnt[i] += cnt[i-1];
		for (int i=n-1; i>=0; --i) sa[--cnt[rank_t2[i]]] = sa_t[i], t[i] = rank_t[i];
		rank_t[sa[0]] = 0;
		p=1;
		for (int i=1; i<n; ++i)
			rank_t[sa[i]] = cmp(t, sa[i], sa[i-1], j) ? p-1 : p++;
	}
	for (int i=0; i<n; ++i) rank[sa[i]] = i;
}

inline void calheight(int n) {
	for (int i=0, k=0; i<n; h[rank[i++]] = k) 
		if(rank[i]) {
			if(k>0) --k;
			for (;s[i+k] == s[sa[rank[i]-1] + k]; ++k);
		} else k=0;
}


int main() {
	scanf("%d", &n);
	scanf("%s", str);
	for (int i=0; i<n; ++i) s[i]=str[i]-'0'+1;
	s[n]=0;
	getsa(n,3);
	calheight(n);
	
	for (int i=0; i<n; ++i) {
		int k=i+1;
		ansn=0;
		for (int j=n-sa[i]; j>h[i]; --j) {
			while(h[k] >= j) k++;
			if (k != i+1) ans[++ansn] = k - i;
		}
		for (int i=ansn; i>=1; --i) printf("%d\n", ans[i]);
	}
	
	return 0;
}

【BZOJ 3172 单词】

# include <stdio.h>
# include <string.h>

using namespace std;

const int M=1600010;
int sa[M], sa_t[M], rank[M], rank_t[M], rank_t2[M], t[M], s[M], cnt[M];
int start[M], length[M], h[M];
char str[M];

inline bool cmp(int *t, int a, int b, int l) {
	return t[a] == t[b] && t[a+l] == t[b+l];
}

inline void getsa(int n, int m) {
	memset(cnt, 0, sizeof(cnt));
	for (int i=0; i<n; ++i) ++cnt[rank_t[i] = s[i]];
	for (int i=1; i<m; ++i) cnt[i] += cnt[i-1];
	for (int i=n-1; i>=0; --i) sa[--cnt[s[i]]] = i;
	for (int j=1, p=1; p<n; j<<=1, m=p) {
		p=0;
		for (int i=n-j; i<n; ++i) sa_t[p++] = i;
		for (int i=0; i<n; ++i) if(sa[i] >= j) sa_t[p++] = sa[i] - j;
		memset(cnt, 0, sizeof(cnt));
		for (int i=0; i<n; ++i) ++cnt[rank_t2[i] = rank_t[sa_t[i]]];
		for (int i=1; i<m; ++i) cnt[i] += cnt[i-1];
		for (int i=n-1; i>=0; --i) sa[--cnt[rank_t2[i]]] = sa_t[i], t[i] = rank_t[i];
		rank_t[sa[0]]=0;
		p=1;
		for (int i=1; i<n; ++i)
			rank_t[sa[i]] = cmp(t, sa[i], sa[i-1], j) ? p-1 : p++;
	}
	for (int i=0; i<n; ++i) rank[sa[i]] = i;
}
inline void geth(int n) {
	for (int i=0, k=0; i<n; h[rank[i++]] = k) {
		if(rank[i]) {
			if(k>0) --k;
			for (; s[i+k] == s[sa[rank[i] - 1] + k]; ++k);
		} else k=0;
	}
}

int n;

int main() {
	scanf("%d", &n);
	int now = 0;
	for (int i=0; i<n; ++i) {
		scanf("%s", str + now);
		start[i] = now;
		now = strlen(str);
		length[i] = now - start[i];
		str[now++] = ' ';
	}
	for (int i=0; i<now; ++i) s[i] = str[i];
	getsa(now, 150);
	geth(now);
	for (int i=0; i<n; ++i) {
		int j, from = rank[start[i]], len = length[i], left, right;
		j = from; for (; j && h[j] >= len; --j);
		left = j;
		j = from+1; for (; j<now && h[j] >= len; ++j);
		right = j;
		printf("%d\n", right - left);
	}
	return 0;
}