首页 > 代码库 > GDOI2012 字符串

GDOI2012 字符串

2024-07-13 19:26:46   212人阅读

2824. 【GDOI2012】字符串(string) (Standard IO)

Time Limits: 1000 ms  Memory Limits: 262144 KB     

Description

mmm正在学习字典序。现在老师给她布置了一个作业：给出一个字符串，问该字符串的所有不同的子串中，按字典序排第K的字串。由于众所周知的原因，mmm需要你为她解决这个问题。

 

Input

 

第1行输入一个只有小写字母组成的字符串。


第2行输入N，为询问个数。


第3到N+2行每行输入一个整数Ki。


 

Output

输出N行，第i行输出按字典序排第Ki的子串，如果Ki超出了子串数量，输出-1.

 

Sample Input

abbb
8
1
2
3
4
5
6
7
8

Sample Output

a
ab
abb
abbb
b
bb
bbb
-1
 

Data Constraint

 
 

Hint

数据范围


1，对于30%的数据，字符串长度≤100


2，对于60%的数据，字符串长度≤3000


3，对于100%的数据，字符串长度≤20000


4，对于100%的数据，1≤N≤10

 

类似于求一个字符串中不同的子串数，直接上sa即可

 

#include<cstdio>#include<cstdlib>#include<algorithm>#include<cmath>#include<cstring>using namespace std;char s[20011];char c;int a[20011],b[20011],sa[20011],co[20011];int rank[20011],h[20011],nr[20011];int i,x,j,k,l,n,m;bool p;int ans[111][3];struct data{    int x,idx;}q[111];bool cmp(data a,data b){    return a.x<b.x;}void Read(){    while(c=getchar(),c<‘a‘||c>‘z‘);    s[++n]=c;    while(c=getchar(),c>=‘a‘&&c<=‘z‘)s[++n]=c;}void sort(int *a){    int i,mn;    if(27>n)mn=27;    else mn=n;    for(i=0;i<=mn;i++)co[i]=0;    for(i=1;i<=n;i++)co[a[i]+1]++;    for(i=1;i<=mn;i++)co[i]+=co[i-1];    for(i=1;i<=n;i++)nr[i]=0;    for(i=1;i<=n;i++){        co[a[sa[i]]]++;        nr[co[a[sa[i]]]]=sa[i];    }    for(i=1;i<=n;i++)sa[i]=nr[i];}void getrank(){    int i;    x=0;    for(i=1;i<=n;i++){        if(i==1||a[sa[i]]!=a[sa[i-1]]||b[sa[i]]!=b[sa[i-1]])x++;        rank[sa[i]]=x;    }}void Suffix(){    int i,j,k,last,l;    for(i=1;i<=n;i++){        sa[i]=i;        a[i]=s[i]-96;        b[i]=0;    }    sort(a);    getrank();    l=1;    while(x!=n){        for(i=1;i<=n;i++){            a[i]=rank[i];            if(i+l<=n)b[i]=rank[i+l];            else b[i]=0;        }        sort(b);        sort(a);        getrank();        l*=2;    }    last=0;    for(i=1;i<=n;i++){        if(last)last--;        if(rank[i]==1)continue;        j=i;        k=sa[rank[i]-1];        while(j+last<=n&&k+last<=n&&s[j+last]==s[k+last])last++;        h[rank[i]]=last;    }}int main(){    Read();    Suffix();    scanf("%d",&m);    for(i=1;i<=m;i++){        scanf("%d",&q[i].x);        q[i].idx=i;    }    sort(q+1,q+1+m,cmp);    l=0;    k=1;    p=true;    for(i=1;i<=m;i++){        while(k<=n&&l+n-sa[k]+1-h[k]<q[i].x){            l=l+n-sa[k]+1-h[k];            k++;        }        if(k>n)p=false;        if(p==false)break;        ans[q[i].idx][1]=sa[k];        ans[q[i].idx][2]=sa[k]+h[k]+q[i].x-l-1;    }    for(j=i;j<=m;j++){        ans[q[i].idx][1]=-1;    }    for(i=1;i<=m;i++){        if(ans[i][1]==-1)printf("-1\n");        else{            for(j=ans[i][1];j<=ans[i][2];j++)printf("%c",s[j]);            printf("\n");        }    }}


联系
我们