首页 > 代码库 > 后缀数组
后缀数组
先说后缀是啥：后缀就是一个串s从第s[i]一直到串尾就是这个串的一个后缀，记作suffix[i]
举个栗子：aacbds的后缀分别为aacbds,acbds,cbds,ds,ds,s（这是回音你懂吗 是回音你懂吗 回音你懂吗 音你懂吗 你懂吗 懂吗 吗）
后缀数组实质就是给每个后缀排个序
比如上面内个串（aacbds，不是回音内个），它的后缀数组就是{1,2,4,3,5,6}
把每个后缀一个一个拿出来排太慢，会T掉，这个时候就要用到强大的倍增算法
倍增求后缀数组：
本质就是从1开始倍增一个l，把rank[i]和rank[i+l]看做是一个长度为2的串（如果i+l>=n呢么rank[i+l]=0），给这个长度为2的串排下序，在根据这次拍的序继续倍增然后继续排
为什么呐，因为字符串排序是从前往后优先级逐渐递减，内个长度为2的串就相当于把一个串拆卡，拆开的部分的名次前面已经求出来了（因为倍增的长度依次*2，所以从中间拆两半拆出来的名次前面一定求过），而且内个长度为2的串是个串，所以优先级也是前面的大（如果看不懂可以自己画下图，或者直接看内个超级经典的图（基本上有关后缀数组的教程都有内个图，是国家集训队论文的图））
排内个长度为2的串一般用桶排序，非常方便
下面是加上注释的代码，我的代码缩行了，而且用了一些省略的写法，看不懂的同学可以去网上搜索其它版本的代码
1 int n; char s[1100]; 2 int rank[1100],height[1100]; 3 int cnt[1100],cnt_rank[1100];//桶 4 int rank1[1100],rank2[1100];//要拼成长度为2的串的两个名次 5 int SA[1100],temp_SA[1100];//表示rank[i]是从下标为几的字符开始的 6 void get_suffix_rank(){ 7 memset(cnt,0,sizeof(cnt)); 8 for(int i=0;i<n;i++) cnt[s[i]]++;//计数 9 for(int i=1;i<=210;i++) cnt[i]+=cnt[i-1];//把名次堆起来10 //因为这个版本的名次是堆的，所以a,a,b,b,c的名次分别是1,1,3,3,411 for(int i=0;i<n;i++) rank[i]=cnt[s[i]]-1;//因为搞了个‘$‘所以要-1让‘$‘的名次为012 for(int l=1;l<n;l*=2){//倍增长度13 for(int i=0;i<n;i++){ rank1[i]=rank[i]; rank2[i]=(i+l<n) ? rank[i+l] : 0;}//两个名次拼成一个长度为2的串14 //下面是基数排序，因为长度为2所以直接分成两个写15 memset(cnt_rank,0,sizeof(cnt_rank));16 for(int i=0;i<n;i++) cnt_rank[rank2[i]]++;17 for(int i=1;i<n;i++) cnt_rank[i]+=cnt_rank[i-1];18 for(int i=n-1;i>=0;i--) temp_SA[--cnt_rank[rank2[i]]]=i;//注意这里是n-1到019 memset(cnt_rank,0,sizeof(cnt_rank));20 for(int i=0;i<n;i++) cnt_rank[rank1[i]]++;21 for(int i=1;i<n;i++) cnt_rank[i]+=cnt_rank[i-1];22 for(int i=n-1;i>=0;i--) SA[--cnt_rank[rank1[temp_SA[i]]]]=temp_SA[i];//和上一个相比就是把i换成了temp_SA23 rank[SA[0]]=0;24 for(int i=1;i<n;i++){25 rank[SA[i]]=rank[SA[i-1]];26 rank[SA[i]]+=(rank1[SA[i]]!=rank1[SA[i-1]] || rank2[SA[i]]!=rank2[SA[i-1]]);27 }28 }29 }30 31 int main(){//freopen("ddd.in","r",stdin);32 scanf("%s",&s); n=strlen(s); s[n++]=‘$‘;//最后要搞个这个东西，防止在倍增过程中出现重复的（比如说a要比a$小）
还有一种叫做DC3的算法，复杂度更优，然而我并不会一。一，有兴趣的同学可以去网上搜索，在OI里倍增一般够用了，而且倍增简单得多
然而只是求出后缀数组一般没什么卵用，更多的时候要用到一个叫做height的非常强大的数组
height里面存的是相邻两个后缀的LCP，即最长公共前缀
怎么求呐：
你也可以把每相邻两个后缀从头比较，不会酱紫太慢，会T掉
可以像kmp那样搞，根据前面求出来的height直接跳过不用对比的地方，直接从上一个height开始比
怎么证明我太弱不会，如果哪天我懂了会来补上去
这是代码：
1 void get_height(){2 int _l=0;3 for(int i=0;i<n;i++)if(rank[i]){4 int j=SA[rank[i]-1];5 while(i+_l<n && j+_l<n && s[i+_l]==s[j+_l]) _l++;6 height[rank[i]]=_l;7 _l-=(_l>0);//因为往后推了一位，所以要-18 }9 }
后缀数组还有很多很棒的应用，这个会另开一篇
刚学后缀数组的时候会觉得很难，然而多看几遍，照着标程写的同时一步一步理解，时间长了后缀数组就和线段树一样不过是随手写出来的小工具而已
后缀数组