題目鏈接：點擊查看

題目大意：給出一個字符串，接下來給出 q 個詢問，每次詢問字符串中第 k 大的子串，要求輸出該字串的左右端點，如果有多個答案，輸出左端點最小的一個

題目分析：因為在求出后綴數(shù)組后，sa數(shù)組已經(jīng)保證了升序，且每個后綴中的前綴也按照升序排列，所以我們可以構(gòu)造一個前綴和，因為每一個后綴貢獻的不重復的子串個數(shù)為 n - sa[ i ] - height[ i ]，這樣就能二分找到第k大的子串第一次出現(xiàn)的位置了，為什么說是第一次出現(xiàn)的位置呢？因為在此之后，可能會有與當前子串重復的子串，且在原字符串中更靠左的位置，為了找出最左邊的位置，我們需要枚舉所有可能，所謂所有可能，就是從當前位置開始，往后尋找所有sa數(shù)組與當前的sa數(shù)組的前綴包含了當前子串的位置，具體實現(xiàn)看代碼吧

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<cmath> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;char str[N];int sa[N]; //SA數(shù)組，表示將S的n個后綴從小到大排序后把排好序的 //的后綴的開頭位置順次放入SA中 int t1[N],t2[N],c[N];int rk[N],height[N],len;int s[N];LL sum[N];void build_sa(int s[],int n,int m)//n為添加0后的總長 {int i,j,p,*x=t1,*y=t2;for(i=0;i<m;i++) c[i]=0;for(i=0;i<n;i++) c[x[i]=s[i]]++;for(i=1;i<m;i++) c[i]+=c[i-1];for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;for(j=1;j<=n;j<<=1) {p=0;for(i=n-j;i<n;i++) y[p++]=i;for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;for(i=0;i<m;i++) c[i]=0;for(i=0;i<n;i++) c[x[y[i]]]++;for(i=1;i<m;i++) c[i]+=c[i-1];for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];swap(x,y);p=1,x[sa[0]]=0;for(i=1;i<n;i++) x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+j]==y[sa[i]+j]?p-1:p++;if(p>=n) break;m=p;} }void get_height(int s[],int n)//n為添加0后的總長 {int i,j,k=0;for(i=0;i<=n;i++)rk[sa[i]]=i;for(i=0;i<n;i++) {if(k) k--;j=sa[rk[i]-1];while(s[i+k]==s[j+k]) k++;height[rk[i]]=k;} }void solve(int base=128) {build_sa(s,len+1,base);get_height(s,len); }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);while(scanf("%s",str)!=EOF){len=strlen(str);for(int i=0;i<len;i++)s[i]=str[i]-'a'+1;s[len]=0;solve(30);for(int i=1;i<=len;i++)sum[i]=sum[i-1]+len-sa[i]-height[i];int m;scanf("%d",&m);int l=0,r=0;while(m--){LL k;scanf("%lld",&k);k=(l^r^k)+1;if(k>sum[len]){printf("%d %d\n",l=0,r=0);continue;}int pos=lower_bound(sum+1,sum+1+len,k)-sum;//二分找到包含第一次出現(xiàn)第k大的子串的后綴l=sa[pos];//這里的l是第一次出現(xiàn)的第k大子串的左端點r=len-(sum[pos]-k+1);//右端點int lenn=r-l+1;//長度while(pos+1<=len&&height[pos+1]>=lenn)//枚舉從當前位置開始往后的所有可能sa數(shù)組{pos++;l=min(l,sa[pos]);//維護最小值r=min(r,sa[pos]+lenn-1);}printf("%d %d\n",++l,++r);}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 5008 Boring String Problem(后缀数组+二分)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。