BZOJ1031 后缀数组

Posted on | In , ,

把一个字符串 $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');
}