@OceanEye6年前
08/6
21:44
学习地址的传送门
当然要看我的也是资瓷哒qwq
0x00
前置知识
SA是所有的后缀的排名
\(sa[i] = the i^{th} suffix’s position \)
rank是某后缀对应在SA中的位置
\(rank[i]= find_pos(sa.begin(),sa.end(),i) \)
height是求完SA之后 相邻排名的后缀 最长公共前缀的长度
\(height[i]= lcp( suffix[i] , suffix[sa[rank[i]-1]]) \)
个人认为最难理解的就是双关键字的桶排序……【其实还算好理解？】
menci大佬的实现是先把第二关键字整理成有序的
\( tmp[len- –buc[sec[i]]] = i \)
操作之后tmp就是按照第二关键字排序的一个数组
接下来把第一关键字占的位数存进桶里面
再用tmp这个第二关键字的有序队列 【这个队列是倒着的 是倒着的 是倒着的】
结合第一关键字的桶 可以推出新的SA
最后用SA数组来推出新的rank数组
\(
if(last==empty) rank[sa[i]]=1
\)
如果是第一个那么rank必定为1
\(
if(last->fir==i->fir /and last->sec==i->sec) rank[sa[i]]=rank[last]
\)
如果第一第二关键字都相同那么排名相同
\(
rank[sa[i]]=rank[last]+1
\)
否则依照SA顺序名次+1
//更新last
建议看第二个模板
模板没有注释
需要完整的解释……请跳转至menci的博客【传送门在上面】
没有height只有sa和rank的
|
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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
#include <cstdio> #include <algorithm> #include <cstring> #include <iostream> #include <cstdlib> #include <cmath> #define ll long long #define INF 1000000000 #define For(i,a,b) for(int i=a;i<=b;++i) #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; C=1; cc=getchar(); while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } #undef p using namespace std; #define N 100010 char s[N]; int SA[N],rank[N],h[N]; int buc[N],fir[N],sec[N],tmp[N]; int n; void make_SA() { bool unique; fill(buc,buc+1+n,0); For(i,1,n) buc[s[i]]++; For(i,1,n) buc[i]+=buc[i-1]; For(i,1,n) rank[i]=buc[s[i]-1]+1; for(int pos=1;pos<=n;pos<<=1) { For(i,1,n) fir[i]=rank[i],sec[i]=i+pos>n?0:rank[i+pos]; fill(buc,buc+1+n,0); For(i,1,n) buc[sec[i]]++; For(i,1,n) buc[i]+=buc[i-1]; For(i,1,n) tmp[n- --buc[sec[i]]]=i; fill(buc,buc+1+n,0); For(i,1,n) buc[fir[i]]++; For(i,1,n) buc[i]+=buc[i-1]; for(int j=1,i;j<=n;j++) { i=tmp[j]; SA[buc[fir[i]]--]=i; } For(i,1,n) printf("%d ",tmp[i]); puts(""); unique=true; for(int j=1,i,last=0;j<=n;j++) { i=SA[j]; if(!last) rank[i]=1; else if(fir[last]==fir[i]&&sec[last]==sec[i]) rank[i]=rank[last],unique=false; else rank[i]=rank[last]+1; last=i; } if(unique) break; } } int main() { scanf("%s",s+1); n=strlen(s+1); For(i,1,n) s[i]=s[i]-'a'+1; make_SA(); For(i,1,n) printf("%d\n",rank[i]); return 0; } |
这个是有height，sa和rank的
|
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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include <cstdio> #include <algorithm> #include <cstring> #include <iostream> #include <cstdlib> #include <cmath> #define ll long long #define INF 1000000000 #define For(i,a,b) for(int i=a;i<=b;++i) #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; C=1; cc=getchar(); while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } #undef p using namespace std; #define N 100010 char s[N]; int SA[N],rank[N],h[N],a[N],set[N]; int fir[N],sec[N],buc[N],tmp[N]; int n; void make_SA() { copy(s+1,s+1+n,set+1); sort(set+1,set+1+n); For(i,1,n) a[i]=lower_bound(set+1,set+1+n,s[i])-set; fill(buc,buc+1+n,0); For(i,1,n) buc[a[i]]++; For(i,1,n) buc[i]+=buc[i-1]; For(i,1,n) rank[i]=buc[a[i]-1]+1; bool unique; for(int p=1;p<=n;p<<=1) { For(i,1,n) fir[i]=rank[i],sec[i]=i+p>n?0:rank[i+p]; fill(buc,buc+1+n,0); For(i,1,n) buc[sec[i]]++; For(i,1,n) buc[i]+=buc[i-1]; For(i,1,n) tmp[n- --buc[sec[i]]]=i; fill(buc,buc+1+n,0); For(i,1,n) buc[fir[i]]++; For(i,1,n) buc[i]+=buc[i-1]; for(int j=1,i;j<=n;j++) { i=tmp[j]; SA[buc[fir[i]]--]=i; } unique=true; for(int j=1,i,last=0;j<=n;j++) { i=SA[j]; if(!last) rank[i]=1; else if(fir[i]==fir[last]&&sec[i]==sec[last]) rank[i]=rank[last],unique=false; else rank[i]=rank[last]+1; last=i; } if(unique) break; } for(int i=1,k=0,j;i<=n;i++) { if(rank[i]==1) k=0; else { k>0?--k:k; j=SA[rank[i]-1]; while(i+k<=n&&j+k<=n&&a[i+k]==a[j+k])k++; } h[rank[i]]=k; } for(int i=1;i<=n;i++) printf("%d ",h[i]); puts(""); for(int i=1;i<=n;i++) printf("%d ",SA[i]); puts(""); for(int i=1;i<=n;i++) printf("%d ",rank[i]); puts(""); } int main() { scanf("%s",s+1); n=strlen(s+1); make_SA(); return 0; } |