Boring String Problem Zeronera问题解决
预处理sum数组记录不同字符串的个数。 即sum [ I ]=n-sa [ I ]1- height [ I ] sum [ I-1 ] (n是原始字符串长度)
每个k sum[n]输出0。 这意味着k大于不同子列的总数
否则，找到二分sum数组包含第k个子字符串的sa数组。 也就是说，找到相应子字符串所在的后缀。
l=sa[pos]，r=sa[pos] v height[pos]-1；
但是，该串的开始位置不一定是最小，因此寻找是否沿着sa阵列有更小的答案
至于为什么要往后说，那是因为现在在sa数组中一定是第一次发现子字符串。 如果之后还出现，height数组会覆盖它，所以以后再找
# include bits/stdc.husingnamespacestd； typedef long ll； //sa[i]:的顺序是第I位的是第几个后缀//rk[i]:的第I个后缀的顺序是第几个//height[i]: sa[i]和sa [ I-1 ] const int n=110 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(intI=1； i=m； I ) cnt[i]=0； for(intI=1； i=n； I ) cnt[x[i]]； for(intI=1； i=m； I ) cnt[i]=cnt[i-1]； for(intI=n； I； I----sa[CNT[x[y[I]]]----]=y[I]； }void SA () (n=Strlen ) ) s1； m=300； for(intI=1； i=n； I ) x[i]=s[i]，y[i]=i； rsort (； for(intk=1； k=n； k=1(intp=0； for(intI=n-k1； i=n； I ) y[ p]=i； //第二关键字是空白字符，开头为for(intI=1； i=n； I ) if(sa[I]k ) y[ p]=sa[i]-k； rsort (； swap(x，y )； x[sa[1]]=1，p=1； for(intI=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(intI=1； i=n； I ) rk[sa[i]]=i； 求height height[1]=0； for(intI=1，j=0； i=n； I ) if(j )--j； while(s[Ij]==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(intI=1； i=n； I ) sum [ I ]=n-sa [ I ]1- height [ I ] sum [ I-1 ]； ll=0，r=0，v=0； while(q-- ) Scanf ) ' %lld '，v )； v=(L^R^V ) 1； if(vsum[n] ) l=r=0； ELSE{intpos=lower_bound(sum1，sum 1 n，v )-sum； v-=sum[pos-1]； l=sa[pos]，r=sa[pos] v height[pos]-1； int len=r-l 1； 销售点； wile(height[pos]=len ) if ) { { l=sa [ pos ] } l=sa [ pos ]； r=l len-1； } pos； }printf('%lld%lld(n )，l，r )； } } return 0； }