Submission #2746086
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
const int N=5050;
const int M=10050;
char str[N];
int K;
int ch[M][26],step[M],sum[M],val[M],pre[M],root,cnt,last;
void SAM(int inde,int id)
{
int u=last;last=++cnt;int now=last;
step[now]=id;val[now]=1;
while(u&&!ch[u][inde]) ch[u][inde]=now,u=pre[u];
if(!u) pre[now]=root;
else
{
int v=ch[u][inde];
if(step[u]+1==step[v]) pre[now]=v;
else
{
int av=++cnt;
step[av]=step[u]+1;
memcpy(ch[av],ch[v],sizeof(ch[v]));
pre[av]=pre[v];pre[v]=pre[now]=av;
while(u&&ch[u][inde]==v) ch[u][inde]=av,u=pre[u];
}
}
}
int buc[M],sa[M];
void prepare()
{
for(int i=1;i<=cnt;i++) buc[step[i]]++;
for(int i=1;i<=cnt;i++) buc[i]+=buc[i-1];
for(int i=1;i<=cnt;i++) sa[buc[step[i]]--]=i;
for(int i=cnt;i>=1;i--)
{
int t=sa[i];
val[pre[t]]=1;
}
val[1]=0;
for(int i=cnt;i>=1;i--)
{
int t=sa[i];
sum[t]=val[t];
for(int j=0;j<26;j++) sum[t]+=sum[ch[t][j]];
}
}
void solve(int now,int k)
{
if(k<=val[now]) return ;
k-=val[now];
for(int i=0;i<26;i++)
{
if(sum[ch[now][i]]<k) k-=sum[ch[now][i]];
else
{
printf("%c",'a'+i);
solve(ch[now][i],k);
return ;
}
}
}
int main()
{
scanf("%s",&str[1]);
scanf("%d",&K);
int len=strlen(&str[1]);
last=root=cnt=1;
for(int i=1;i<=len;i++) SAM(str[i]-'a',i);
prepare();
solve(1,K);
return 0;
}
Submission Info
Submission Time
2018-06-26 18:21:24+0900
Task
C - K-th Substring
User
Heey
Language
C++14 (GCC 5.4.1)
Score
300
Code Size
1409 Byte
Status
AC
Exec Time
2 ms
Memory
1024 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:66:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",&str[1]);
^
./Main.cpp:67:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&K);
^
Judge Result
Set Name
Sample
Subtask
All
Score / Max Score
0 / 0
200 / 200
100 / 100
Status
Set Name
Test Cases
Sample
0_000.txt, 0_001.txt, 0_002.txt
Subtask
0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt
All
0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 2_011.txt, 2_012.txt, 2_013.txt, 2_014.txt, 2_015.txt, 2_016.txt, 2_017.txt, 2_018.txt
Case Name
Status
Exec Time
Memory
0_000.txt
AC
1 ms
256 KB
0_001.txt
AC
1 ms
256 KB
0_002.txt
AC
1 ms
256 KB
1_003.txt
AC
1 ms
256 KB
1_004.txt
AC
1 ms
256 KB
1_005.txt
AC
1 ms
256 KB
1_006.txt
AC
1 ms
256 KB
1_007.txt
AC
1 ms
256 KB
1_008.txt
AC
1 ms
256 KB
1_009.txt
AC
1 ms
256 KB
1_010.txt
AC
1 ms
256 KB
2_011.txt
AC
2 ms
896 KB
2_012.txt
AC
2 ms
896 KB
2_013.txt
AC
2 ms
1024 KB
2_014.txt
AC
2 ms
1024 KB
2_015.txt
AC
2 ms
896 KB
2_016.txt
AC
2 ms
1024 KB
2_017.txt
AC
2 ms
1024 KB
2_018.txt
AC
2 ms
1024 KB