【后缀数组】后缀排序

字符串

传送门：UOJ35

后缀数组模板题

思路：倍增+排序求出SA，再线性构造LCP

代码：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 800000
int len,rk[N],sa[N],lcp[N];
char s[N];
struct node{
	int x,y,ID;
	bool operator < (const node a) const{
		return (x<a.x) || (x==a.x && y<a.y);
	}
}c[N];
int main(){
	scanf("%s",s+1);
	len=strlen(s+1);
	for (int i=1;i<=len;i++) c[i]=(node){s[i],0,i};
	sort(c+1,c+len+1);
	for (int i=1,j=0;i<=len;i++){if (c[i-1]<c[i]) j++; rk[c[i].ID]=j;}
	for (int i=len+1;i<=len<<2;i++) rk[i]=-1;
	for (int i=0;rk[c[len].ID]<len;i++){
		for (int j=1;j<=len;j++) c[j]=(node){rk[j],rk[j+(1<<i)],j};
		sort(c+1,c+len+1);
		rk[c[1].ID]=1;
		for (int j=2;j<=len;j++)
			if (c[j-1]<c[j]) rk[c[j].ID]=rk[c[j-1].ID]+1;
			else rk[c[j].ID]=rk[c[j-1].ID];
	}
	for (int i=1;i<=len;i++) sa[rk[i]]=i; int h=0;
	for (int i=1;i<len;i++){
		int j=sa[rk[i]-1];
		if (h) h--;
		while (i+h<=len && j+h<=len && s[i+h]==s[j+h]) h++;
		lcp[rk[i]-1]=h;
	}
	for (int i=1;i<=len;i++) printf("%d ",sa[i]); puts("");
	for (int i=1;i<len;i++) printf("%d ",lcp[i]); puts("");
	return 0;
}