BZOJ1031 后缀数组

把一个字符串 $S$ 排成一圈,从每个字符开始读一圈,把每次读到的字符串排序,按顺序将每个串的最后一个字符排成一个新字符串,求新字符串。($|S|\le10^5$)


分析

  • 对于任意一个字符串,没有两个相同的后缀。
  • 按照题意需要比较长度为len的字符串,故直接将s赋值一遍,考虑[1.len]的sa[i],直接从小到大输出即可,因为后缀比较len长度一定可以比较出来

题解

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
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
using namespace std;

//sa:字典序中排第i位的起始位置在str中第sa[i] sa[1~n]为有效值,取值范围为[0,len-1]
//rank:就是str第i个位置的后缀是在字典序排第几 rank[0~n-1]为有效值
//height:字典序排i和i-1的后缀的最长公共前缀 height[2~n]为有效值,第二个到最后一个

const int maxn = 2e5+5;//开总串长度,不要忘记连接符
int wa[maxn],wb[maxn],wsf[maxn],wv[maxn],sa[maxn],rk[maxn],ht[maxn],ns[maxn];
char hs[maxn];

int cmp(int *r,int a,int b,int k)
{
return r[a]==r[b]&&r[a+k]==r[b+k];
}

void getsa(int *r,int *sa,int n,int m) //n为添加0后的总长
{
int i,j,p,*x=wa,*y=wb,*t;
for(i=0; i<m; i++) wsf[i]=0;
for(i=0; i<=n; i++) wsf[x[i]=r[i]]++;
for(i=1; i<m; i++) wsf[i]+=wsf[i-1];
for(i=n; i>=0; i--) sa[--wsf[x[i]]]=i;
p=1;
j=1;
for(; p<=n; j*=2,m=p)
{
for(p=0,i=n+1-j; i<=n; i++) y[p++]=i;
for(i=0; i<=n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;
for(i=0; i<=n; i++) wv[i]=x[y[i]];
for(i=0; i<m; i++) wsf[i]=0;
for(i=0; i<=n; i++) wsf[wv[i]]++;
for(i=1; i<m; i++) wsf[i]+=wsf[i-1];
for(i=n; i>=0; i--) sa[--wsf[wv[i]]]=y[i];
t=x; x=y; y=t;
x[sa[0]]=0;
for(p=1,i=1; i<=n; i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)? p-1:p++;
}
}

void getht(int *r,int n) //n为添加0后的总长
{
int i,j,k=0;
for(i=1; i<=n; i++) rk[sa[i]]=i;
for(i=0; i<n; i++)
{
if(k)k--;
else k=0;
j=sa[rk[i]-1];
while(r[i+k]==r[j+k]) k++;
ht[rk[i]]=k;
}
}
int main()
{
scanf("%s", hs);
int len =strlen(hs);
for(int i=0;i<len;i++)
ns[i+len]=ns[i]=int(hs[i]);
for(int i=0;i<len;i++)
hs[i+len]=hs[i];
len*=2;
ns[len]=0;
getsa(ns, sa, len, 600);
for (int i = 1; i <= len; i++) {
if(sa[i]<len/2)
{
printf("%c", hs[sa[i]+len/2-1]);
}
}
putchar('\n');
}