Boring String Problem

Zeronera題解
預處理sum數組記錄不同字符串的個數，即sum[i] = n- sa[i] + 1 -height[i] + sum[i-1] (n為原串長度)

對于每個k 若k > sum[n] 則輸出0 0 ，即k大于不同子串的總數

否則，二分sum數組找到第k小子串所在的sa數組，即找到相應子串所位于的后綴。
l=sa[pos],r=sa[pos]+v+height[pos]-1;

但是該串的開始位置不一定是最小的，所以順著sa數組要往后找是否還有更小的答案

至于為什么只要往后，因為當前找到子串的一定是該串在sa數組中第一次，之后若還出現，height數組會將其覆蓋，所以要往后找

#include<bits/stdc++.h> using namespace std; typedef long long ll; // sa[i]: 排名是i位的是第幾個后綴 // rk[i]: 第i個后綴的排名是多少 // height[i]: sa[i]與sa[i-1] const int N=100010; char s[N]; int rk[N],sa[N],cnt[N],height[N]; int x[N],y[N]; int n,m; void rsort()// x[i] 第一關鍵字 y[i] 第二關鍵字 基數排序 {for(int i=1;i<=m;i++) cnt[i]=0;for(int i=1;i<=n;i++) cnt[x[i]]++;for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];for(int i=n;i;i--) sa[cnt[x[y[i]]]--]=y[i]; } void SA() {n=strlen(s+1);m=300;for(int i=1;i<=n;i++) x[i]=s[i],y[i]=i;rsort();for(int k=1;k<=n;k<<=1){int p=0;for(int i=n-k+1;i<=n;i++) y[++p]=i;// 第二關鍵字為空字符排在最前面for(int i=1;i<=n;i++) if(sa[i]>k) y[++p]=sa[i]-k;rsort();swap(x,y);x[sa[1]]=1,p=1;for(int i=2;i<=n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p:++p);if(p==n) break;m=p;}for(int i=1;i<=n;i++) rk[sa[i]]=i;// 求heightheight[1]=0;for(int i=1,j=0;i<=n;i++){if(j) --j;while(s[i+j]==s[sa[rk[i]-1]+j]) j++;height[rk[i]]=j;} } ll sum[N];int q; int main() {while(~scanf("%s%d",s+1,&q)){SA();for(int i=1;i<=n;i++) sum[i]=n-sa[i]+1-height[i]+sum[i-1];ll l=0,r=0,v=0;while(q--){scanf("%lld",&v);v=(l^r^v)+1;if(v>sum[n]) l=r=0;else{int pos=lower_bound(sum+1,sum+1+n,v)-sum;v-=sum[pos-1];l=sa[pos],r=sa[pos]+v+height[pos]-1;int len=r-l+1;pos++;while(height[pos]>=len){if(l>sa[pos]){l=sa[pos];r=l+len-1;}pos++;}}printf("%lld %lld\n",l,r);}}return 0; }

總結

以上是生活随笔為你收集整理的HDU 5008 Boring String Problem ( 后缀数组求本质不同第k大子串)的全部內容，希望文章能夠幫你解決所遇到的問題。

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