Submission #2504539
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
char ss[5010];
int k, s[5010], sa[5010], rk[5010], height[5010];
int g(int x, int n0)
{
return x < n0 ? x * 3 + 1 : (x - n0) * 3 + 2;
}
void radix(int *a, int *b, int *s, int n, int K)
{
int *hh = new int[K + 1];
for (int i = 0; i <= K; i++)
hh[i] = 0;
for (int i = 0; i < n; i++)
hh[s[a[i]]]++;
for (int i = 1; i <= K; i++)
hh[i] += hh[i - 1];
for (int i = n - 1; i >= 0; i--)
b[--hh[s[a[i]]]] = a[i];
}
void dc3(int *s, int *sa, int n, int K)
{
int n0 = (n + 2) / 3, n1 = (n + 1) / 3, n2 = n / 3, n02 = n0 + n2;
int *s12 = new int[n02 + 3];
s12[n02] = s12[n02 + 1] = s12[n02 + 2] = 0;
int *sa12 = new int[n02 + 3];
sa12[n02] = sa12[n02 + 1] = sa12[n02 + 2] = 0;
int *s0 = new int[n0];
int *sa0 = new int[n0];
for (int i = 0, hh = 0; i < n; i++)
if (i % 3)
s12[hh++] = i;
if (n % 3 == 1)
s12[n02 - 1] = n;
radix(s12, sa12, s + 2, n02, K);
radix(sa12, s12, s + 1, n02, K);
radix(s12, sa12, s, n02, K);
int name = 0, c1 = -1, c2 = -1, c3 = -1;
for (int i = 0; i < n02; i++)
{
if (c1 != s[sa12[i]] || c2 != s[sa12[i] + 1] || c3 != s[sa12[i] + 2])
{
c1 = s[sa12[i]];
c2 = s[sa12[i] + 1];
c3 = s[sa12[i] + 2];
name++;
}
if (sa12[i] % 3 == 1)
s12[sa12[i] / 3] = name;
else
s12[sa12[i] / 3 + n0] = name;
}
if (name < n02)
{
// s12[n02] = s12[n02 + 1] = s12[n02 + 2] = 0;
dc3(s12, sa12, n02, name);
for (int i = 0; i < n02; i++)
s12[sa12[i]] = i + 1;
}
else
{
for (int i = 0; i < n02; i++)
sa12[s12[i] - 1] = i;
}
for (int i = 0, hh = 0; i < n02; i++)
if (sa12[i] < n0)
s0[hh++] = sa12[i] * 3;
radix(s0, sa0, s, n0, K);
int i = n0 - n1, j = 0, hh = 0;
while (i < n02 && j < n0)
{
if (sa12[i] < n0 && make_pair(s[g(sa12[i], n0)], s12[sa12[i] + n0]) < make_pair(s[sa0[j]], s12[sa0[j] / 3]) ||
sa12[i] >= n0 && make_tuple(s[g(sa12[i], n0)], s[g(sa12[i], n0) + 1], s12[sa12[i] + 1 - n0]) < make_tuple(s[sa0[j]], s[sa0[j] + 1], s12[sa0[j] / 3 + n0]))
sa[hh++] = g(sa12[i++], n0);
else
sa[hh++] = sa0[j++];
}
while (i < n02)
sa[hh++] = g(sa12[i++], n0);
while (j < n0)
sa[hh++] = sa0[j++];
delete[] s12;
delete[] sa12;
delete[] s0;
delete[] sa0;
}
int main()
{
scanf("%s%d", ss, &k);
int n = strlen(ss);
for (int i = 0; i < n; i++) s[i] = ss[i] - 'a' + 1;
dc3(s, sa, n, 26);/*
for (int i = 0; i < n; i++)
{
for (int j = sa[i]; j < n; j++) printf("%c", ss[j]);
puts("");
}*/
sa[n] = n;
for (int i = 0; i < n; i++)
rk[sa[i]] = i;
for (int i = 0, k = 0; i < n; i++)
{
if (k) k--;
int j = sa[rk[i] + 1];
while (s[i + k] == s[j + k])
k++;
height[rk[i]] = k;
}
for (int i = 0; i < n; i++)
{
int hh = i ? height[i - 1] : 0;
if (k > n - sa[i] - hh) k -= n - sa[i] - hh;
else
{
// printf("%d %d %d\n", i, sa[i], k);
for (int j = 0; j < k + hh; j++)
printf("%c", ss[sa[i] + j]);
break;
}
}
puts("");
}
Submission Info
Submission Time
2018-05-12 22:47:15+0900
Task
C - K-th Substring
User
tkj
Language
C++14 (GCC 5.4.1)
Score
300
Code Size
3192 Byte
Status
AC
Exec Time
2 ms
Memory
384 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:91:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s%d", ss, &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
384 KB
2_012.txt
AC
2 ms
384 KB
2_013.txt
AC
2 ms
384 KB
2_014.txt
AC
2 ms
384 KB
2_015.txt
AC
1 ms
384 KB
2_016.txt
AC
2 ms
384 KB
2_017.txt
AC
2 ms
384 KB
2_018.txt
AC
2 ms
384 KB