后缀数组

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <stack>
 9 #include <queue>
10 #include <set>
11 #include <map>
12 #include <math.h>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const int mod=1e9+7;
16 const int maxn=1e6+10;
17 using namespace std;
18 
19 char str[maxn];
20 int sa[maxn];//排名为i的后缀的位置
21 int rk[maxn];//从第i个位置开始的后缀的排名
22 int C[maxn];//C数组表示桶，统计每种元素出现了多少次，辅助基数排序 
23 int X[maxn];//X[i]是第i个元素的第一关键字的字典排名 
24 int Y[maxn];//Y[i]表示在第二关键字中排名为i的数，其第一关键字的位置
25 
26 int n,m;
27 void Get_SA()
28 {
29     for(int i=1;i<=n;i++)
30         C[X[i]=str[i]]++;
31     for(int i=2;i<=m;i++)//做C的前缀和，我们就可以得出每个关键字最多是在第几名
32         C[i]+=C[i-1];
33     for(int i=n;i>=1;i--)
34         sa[C[X[i]]--] = i;
35     
36     for(int k = 1; k <= n; k <<= 1)
37     {//k:当前倍增的长度，k = x表示已经求出了长度为x的后缀的排名，现在要更新长度为2x的后缀的排名
38         int num=0; //num仅仅是一个计数器,示不同的后缀的个数，很显然原字符串的后缀都是不同的，因此num=n时可以退出循环
39         
40         for(int i=n-k+1;i<=n;i++)//第n-k+1到第n位是没有第二关键字的 所以排名在最前面
41             Y[++num]=i;
42         for(int i=1;i<=n;i++)
43             if(sa[i]>k)
44                 Y[++num]=sa[i]-k;
45 //排名为i的数 在数组中是否在第k位以后,即满足(sa[i]>k)，那么它可以作为别人的第二关键字，就把它的第一关键字的位置添加进Y就行了
46 //所以i枚举的是第二关键字的排名，第二关键字靠前的先入队
47 
48         for(int i=1;i<=m;i++)
49             C[i]=0;//初始化C桶
50         for(int i=1;i<=n;i++)
51             C[X[Y[i]]]++;
52         //因为上一次循环已经算出了这次的第一关键字 所以直接加就行了
53         for(int i=1;i<=m;i++)
54             C[i]+=C[i-1];//第一关键字排名为1~i的数有多少个
55         for(int i=n;i>=1;i--)
56             sa[C[X[Y[i]]]--]=Y[i];
57 //因为Y的顺序是按照第二关键字的顺序来排的,第二关键字靠后的，在同一个第一关键字桶中排名越靠后
58 
59         swap(X,Y);//这里不用想太多，因为要生成新的X时要用到旧的，就把旧的复制下来，没别的意思
60         num=1;
61         X[sa[1]]=1;
62         for(int i=2;i<=n;i++)//因为sa[i]已经排好序了，所以可以按排名枚举，生成下一次的第一关键字X; 
63             X[sa[i]]=(Y[sa[i]]==Y[sa[i-1]] && Y[sa[i]+k]==Y[sa[i-1]+k]) ? num : ++num;
64         if(num==n)
65             break;
66         m=num;//这里就不用那个122了，因为都有新的编号了
67     }
68 }
69 
70 int main()
71 {
72     gets(1+str);
73     n=strlen(1+str);
74     m=122;
75     Get_SA();
76     for(int i=1;i<=n;i++)
77     {
78         if(i==1)
79             printf("%d",sa[i]);
80         else
81             printf(" %d",sa[i]);
82     }
83     printf("\n");
84     return 0;
85 }