首页 > 代码库 > 后缀数组-Codevs1500

后缀数组-Codevs1500

      后缀数组的原理很简单,将一个字符串S的所有后缀组成一个字符串数组,并排序,则以后每次判断某个字符串D是不是S的子串只需要strlen(D)*log(strlen(s))的时间复杂度。Codevs1500这题就是一道裸题,考后缀数组的生成,如果一个一个将S的后缀加入到后缀数组中并快速排序需要的时间复杂度为(n的平方*log n),效率极低。一般可以用倍增法将生成后缀数组的时间复杂度优化到(n*log n*log n)。
      倍增法的思想一开始觉得有点难理解,先只比较每个后缀的第一个字母,得到一个顺序列表,然后再利用之前得到的顺序列表比较每个后缀的前两个字母,然后再利用比较前两个字母得到的顺序列表比较前4个字母。。就这样一直比较到前(2^k)个字母,当(2^k)>=原字符串的长度时即可停止。假设我们当前已经得到了只比较前x个字母的顺序列表,要比较2个后缀前2x个字母的顺序时只需要先比较这两个后缀的前x个字母的顺序,如果相同再比较这两个后缀第x+1个字母到第2x个字母的顺序,由于要比较的字符串的长度都为x,所以可以利用之前得到的只比较后缀的前x个字母的顺序列表来实现快速的比较2个后缀的前2x个字母的顺序,比较一次的时间复杂度为O(1)。

贴个代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<algorithm>
 6 #define maxn 16000
 7 using namespace std;
 8 char s[maxn];
 9 int n,order[2*maxn];
10 struct An_Suffix{
11        int st,len;
12        friend bool operator < (const An_Suffix a,const An_Suffix b){
13               if(a.len==1) return s[a.st]<s[b.st];
14               if(order[a.st]!=order[b.st]) return order[a.st]<order[b.st];
15               return order[a.st+(a.len/2)]<order[b.st+(b.len/2)];
16        }
17        friend bool operator == (const An_Suffix a,const An_Suffix b){
18               if(a.len==1) return s[a.st]==s[b.st];
19               return (order[a.st]==order[b.st] && order[a.st+(a.len/2)]==order[b.st+(b.len/2)]);
20        }
21 }suff[maxn];
22 struct An_Order{
23        int n,order;
24        friend bool operator < (const An_Order a,const An_Order b){
25               return a.order<b.order;
26        }
27 }ans[maxn];
28 void get_order(int len){
29      int order2[maxn];
30      for(int i=0;i<n;i++) suff[i]=((An_Suffix){i,len});
31      sort(suff,suff+n);
32      int t=1;order2[suff[0].st]=t;
33      for(int i=1;i<n;i++){
34              if(!(suff[i-1]==suff[i])) t++;
35              order2[suff[i].st]=t;
36      }
37      for(int i=0;i<n;i++) order[i]=order2[i];
38 }         
39 int main(){
40     scanf("%d",&n);
41     scanf("%s",s);
42     int t=1;
43     while(1){
44              get_order(t);
45              if(t>=n) break;
46              t=t*2;
47     }
48     for(int i=0;i<n;i++) ans[i]=((An_Order){i,order[i]});
49     sort(ans,ans+n);
50     for(int i=0;i<n;i++) printf("%d\n",ans[i].n+1);
51     return 0;
52 }

ans是用来记录每个点的顺序的,用来输出答案。数据结构An_Suffix中 重载的“<”用来判断两个后缀在当前的比较长度下的先后顺序,重载的“==”判断两个后缀在当前的比较长度下是否相等。注意order数组一定要开到2*maxn,因为当比较长度为2*(n-1)时,在对以最后一个字符为起点的后缀操作时,有可能访问到order[st+len/2],此时这个值应当默认为0。

后缀数组-Codevs1500