SPOJ 7258 SUBLEX 后綴數組_二分答案_前綴和

Code:

#include <cstdio> #include <algorithm> #include <cstring> #define setIO(s) freopen(s".in","r",stdin) #define maxn 1000000 #define ll long long using namespace std; char str[maxn]; int arr[maxn],pos[maxn],x[maxn],rk[maxn],sa[maxn],c[maxn],height[maxn]; ll C[maxn],brr[maxn]; int n,m; struct SA{void qsort(){for(int i=0;i<=m;++i) c[i]=0;for(int i=1;i<=n;++i) ++c[rk[pos[i]]];for(int i=1;i<=m;++i) c[i]+=c[i-1];for(int i=n;i>=1;--i) sa[c[rk[pos[i]]]--]=pos[i]; }void build(){for(int i=1;i<=n;++i) rk[i]=arr[i],pos[i]=i; qsort();for(int k=1;k<=n;k<<=1){int num=0;for(int i=n-k+1;i<=n;++i) pos[++num]=i;for(int i=1;i<=n;++i) if(sa[i]>k) pos[++num]=sa[i]-k; qsort();swap(rk,pos);rk[sa[1]]=1,num=1;for(int i=2;i<=n;++i)rk[sa[i]]=(pos[sa[i]]==pos[sa[i-1]]&&pos[sa[i]+k]==pos[sa[i-1]+k])?num:++num;if(num==n) break;m=num; }}void get_height(){int k=1;for(int i=1;i<=n;++i) rk[sa[i]]=i; for(int i=1;i<=n;++i){if(k) --k;int j=sa[rk[i]-1];while(arr[i+k]==arr[j+k]) ++k;height[rk[i]]=k; }} }T; int main(){//setIO("input"); scanf("%s",str),n=strlen(str),m=128;for(int i=1;i<=n;++i) arr[i]=str[i-1]; T.build(),T.get_height(); for(int i=1;i<=n;++i) brr[i]=n-sa[i]+1-height[i];for(int i=1;i<=n;++i) C[i]=C[i-1]+brr[i];int q; long long opt; scanf("%d",&q);while(q--){scanf("%lld",&opt);int l=1,r=n,mid,ans=0; while(l<=r) {mid=(l+r)>>1;if(C[mid]>=opt) ans=mid,r=mid-1;else l=mid+1;}for(int i=sa[ans];i<=n-(C[ans]-opt);++i) printf("%c",str[i-1]); printf("\n");}return 0; }

　　

posted @ 2019-01-16 22:56 EM-LGH 閱讀(...) 評論(...) 編輯 收藏

總結

以上是生活随笔為你收集整理的SPOJ 7258 SUBLEX 后缀数组_二分答案_前缀和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。