后缀数组SA

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134042245

https://uoj.ac/problem/35

通过倍增实现排序

类似基数排序，先排后面，再排前面

排的过程可以拿桶排优化

  • 设 h(i)=lcp(sa[rk[i]−1],i)h(i)=lcp(sa[rk[i]-1],i)

  • 有 h(i)≥h(i−1)−1h(i)\ge h(i-1)-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 2000010
//#define M
//#define mo
int n, m, i, j, k, T;
int tmp[N], bin[N], rk[N], sa[N], tot; 
int h[N]; 
char s[N]; 

void psort() {
	memset(bin, 0, sizeof(bin)); 
	int i; 
	for(i=1; i<=n; ++i) bin[rk[i]]++; 
	for(i=1; i<=max(n, 218); ++i) bin[i]+=bin[i-1]; 
	for(i=n; i>=1; --i) sa[bin[rk[tmp[i]]]--]=tmp[i]; 
}

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}
	scanf("%s", s+1); n=strlen(s+1);  
	for(i=1; i<=n; ++i) rk[i]=s[i], tmp[i]=i; 
	psort(); 
//	for(i=1; i<=n; ++i) printf("%lld ", sa[i]); printf("\n"); 
	for(j=1; j<n; j<<=1) {
		for(i=n-j+1, k=0; i<=n; ++i) tmp[++k]=i; 
		for(i=1; i<=n; ++i) if(sa[i]-j>0) tmp[++k]=sa[i]-j; 
		psort(); 
		tmp[sa[1]]=tot=1; 
		for(i=2; i<=n; ++i) {
			if(rk[sa[i]]!=rk[sa[i-1]] || rk[sa[i]+j]!=rk[sa[i-1]+j]) ++tot; 
			tmp[sa[i]]=tot; 
		}
		memcpy(rk, tmp, sizeof(tmp)); 
	}
	for(i=1; i<=n; ++i) printf("%d ", sa[i]); printf("\n"); 
	for(i=1; i<=n; ++i) {
		h[i]=max(h[i-1]-1, 0); 
		j = sa[rk[i]-1]; 
		while(s[i+h[i]] == s[j+h[i]]) ++h[i]; 
	}
	for(i=2; i<=n; ++i) printf("%d ", h[sa[i]]); 
	return 0;
}