后缀数组的倍增算法

一、基数排序。

题目描述：给你n个字符串，把它们排序。 n<=100000 （不要用sort水过，除非你在NOI的考场上）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<cmath>
 6 #include<ctime>
 7 #include<algorithm>
 8 #define MAXN 100010
 9 using namespace std;
10 int n,rank[MAXN],p[MAXN],sa[MAXN],cnt[MAXN];
11 char s[MAXN][15];
12 inline int read()
13 {
14     int x=0,f=1;  char ch=getchar();
15     while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
16     while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
17     return x*f;
18 }
19 void Init()
20 {
21     n=read();
22     for(int i=1;i<=n;i++)
23     {
24         char ch[15];
25         scanf("%s",ch);
26         for(int j=1;j<=10;j++)
27             s[i][j]=j>strlen(ch)?'a'-1:ch[j-1];
28     }
29 }
30 void Radix_sort()
31 {
32     for(int i=1;i<=n;i++)  sa[i]=i;
33     for(int l=10;l>0;l--)
34     {
35         for(int i=1;i<=n;i++)  rank[i]=s[i][l]-'a'+1,p[i]=sa[i];
36         for(int i=0;i<=26;i++)  cnt[i]=0;
37         for(int i=1;i<=n;i++)  cnt[rank[i]]++;
38         for(int i=1;i<=26;i++)  cnt[i]+=cnt[i-1];
39         for(int i=n;i>=1;i--)  sa[cnt[rank[p[i]]]--]=p[i];
40     }
41 }
42 void print()
43 {
44     for(int i=1;i<=n;i++)
45         printf("%d ",sa[i]);
46 }
47 int main()
48 {
49     Init();
50     Radix_sort();
51     print();
52     return 0;
53 }

View Code

二、求后缀数组。

 1 int N,ans,rank[MAXN],sa[MAXN],p[MAXN],cnt[MAXN],tmp[MAXN],height[MAXN];
 2 char s[MAXN];
 3 bool equ(int x,int y,int l) {return rank[x]==rank[y]&&rank[x+l]==rank[y+l];}
 4 void doubling()
 5 {
 6     for(int i=1;i<=N;i++)  rank[i]=s[i],sa[i]=i;
 7     for(int pos=0,sig=255,l=0,i;pos<N;sig=pos)
 8     {
 9         for(i=N-l+1,pos=0;i<=N;i++)  p[++pos]=i;
10         for(i=1;i<=N;i++)  if(sa[i]>l)  p[++pos]=sa[i]-l;
11         for(i=1;i<=sig;i++)  cnt[i]=0;
12         for(i=1;i<=N;i++)  cnt[rank[i]]++;
13         for(i=1;i<=sig;i++)  cnt[i]+=cnt[i-1];
14         for(i=N;i;i--)  sa[cnt[rank[p[i]]]--]=p[i];
15         for(pos=0,i=1;i<=N;i++)  
16             tmp[sa[i]]=equ(sa[i],sa[i-1],l)?pos:++pos;
17         for(int i=1;i<=N;i++)  rank[i]=tmp[i];
18         l=!l?1:l<<1;
19     }
20 }

View Code

三、height数组

 1 void get_height()
 2 {
 3     for(int i=1,j=0,k;i<=N;i++)
 4     {
 5         if(!(k=sa[rank[i]-1]))  {j=0;  continue;}
 6         if(j)  j--;
 7         while(s[i+j]==s[k+j])  j++;
 8         height[rank[i]]=j;
 9         ans=max(ans,j);
10     }
11 }

View Code