Submission #2495092

---

Source Code Expand

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std;
const int maxn=100100;
const int INF=0x3f3f3f3f;

int a[maxn],b[maxn],c[maxn],d[maxn];
int s[maxn],n;
int sa[maxn],h[maxn],rk[maxn];
int sum[maxn];
char str[maxn];
bool cmp(int r[],int a,int b,int k){
	return r[a]==r[b]&&r[a+k]==r[b+k];
}
void build_sa(int r[],int sa[],int n,int m){
	int i,j,p,*x=a,*y=b;
	for(i=0;i<m;c[i++]=0);
	for(i=0;i<n;c[x[i++]=r[i-1]]++);
	for(i=0;i<m;c[++i]+=c[i-1]);
	for(i=n-1;i>=0;sa[--c[x[i]]]=i--);
	for(j=1,p=1;p<n;j<<=1,m=p){
		for(p=0,i=n-j;i<n;y[p++]=i++);
		for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
		for(i=0;i<n;d[i++]=x[y[i-1]]);
		for(i=0;i<m;c[i++]=0);
		for(i=0;i<n;c[d[i++]]++);
		for(i=0;i<m;c[++i]+=c[i-1]);
		for(i=n-1;i>=0;sa[--c[d[i--]]]=y[i+1]);
		for(swap(x,y),p=1,x[sa[0]]=0,i=1;i<n;i++)
			x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
	}
}
void calh(int r[],int sa[],int n){
	int i,j,k=0;
	for(i=1;i<=n;rk[sa[i++]]=i-1);
	for(i=0;i<n;h[rk[i++]]=k)
		for(k?k--:0,j=sa[rk[i]-1];r[i+k]==r[j+k];k++);
}
int main(){
	int Q;
	scanf("%s",str);
	n=strlen(str);
	for(int i=0;i<n;i++)s[i]=(int)str[i];
	s[n]=0;
	build_sa(s,sa,n+1,256);
	calh(s,sa,n);
	
	int tot=0;
	for(int i=1;i<=n;i++){
		sum[i] = n-sa[i]-h[i];
		tot+=sum[i];
	}
	for(int i=2;i<=n;i++)
		sum[i]+=sum[i-1];
	int kth,ans;
	cin>>kth;
	if(kth>tot)kth%=tot;
	int L=0,R=n,mid;	
	while(L<=R){
		mid=(L+R)>>1;
		if(sum[mid]>=kth){
			ans=mid;R=mid-1;
		}else L=mid+1;
	}
	int s=sa[ans];
	int t=s+kth-sum[ans-1]+h[ans]-1;
	for(int i=s;i<=t;i++)cout<<str[i];
	cout<<endl;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:43:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",str);
                 ^

Judge Result