后缀数组模版
正文索引 [隐藏]
简介
给定一个 $0-Based$ 字符串 Str，将它的所有后缀进行排序。
数组 $sa[i]$ 中保存排名第 $i$ 的后缀的在字符串的那个位置，数组 $rank[i]$ 表示从位置 i 开始的子串的排名。
数组 $height[i]$ 表示排名第 $i$ 的字符串和排名第 $i+1$ 的字符串的公共前缀长度。
代码
|
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 |
namespace SuffixArray{ const int Maxn=1e5+50; int cnt[Maxn+5]; inline void radix(int str[],int pos[],int sa[],int n,int m){ memset(cnt,0,sizeof(cnt)); for (int i=0;i<n;i++) cnt[str[pos[i]]]++; for (int i=1;i<=m;i++) cnt[i]+=cnt[i-1]; for (int i=n-1;i>=0;i--) sa[--cnt[str[pos[i]]]]=pos[i]; } int rank[Maxn+5],a[Maxn+5],b[Maxn+5]; inline void SA(int str[],int sa[],int n,int m){ for (int i=0;i<n;i++) rank[i]=i; radix(str,rank,sa,n,m); rank[sa[0]]=0; for (int i=1;i<n;i++) rank[sa[i]] = rank[sa[i-1]] + (str[sa[i]]!=str[sa[i-1]]); for (int k=1;k<=n;k<<=1){ for (int j=0;j<n;j++){ a[j]=rank[j]+1; b[j]=(j+k>=n?0:rank[j+k]+1); sa[j]=j; } radix(b,sa,rank,n,n); radix(a,rank,sa,n,n); rank[sa[0]]=0; for (int i=1;i<n;i++) rank[sa[i]] = rank[sa[i-1]] + (a[sa[i]]!=a[sa[i-1]] || b[sa[i]]!=b[sa[i-1]]); } } inline void getHeight(int str[],int sa[],int rank[],int height[],int n){ for (int i=0;i<n;i++) rank[sa[i]]=i; int k=0; height[0]=0; for (int i=0;i<n;i++){ k=(k==0?0:k-1); if (rank[i]!=0) while(str[i+k]==str[sa[rank[i]-1]+k]) k++; height[rank[i]]=k; } } } |
还没有任何评论，你来说两句吧!