| Task: | Repeating substring |
| Sender: | sfjiang |
| Submission time: | 2020-09-26 14:20:04 +0300 |
| Language: | C++ (C++11) |
| Status: | READY |
| Result: | WRONG ANSWER |
| test | verdict | time | |
|---|---|---|---|
| #1 | WRONG ANSWER | 0.01 s | details |
| #2 | WRONG ANSWER | 0.00 s | details |
| #3 | RUNTIME ERROR | 0.01 s | details |
| #4 | RUNTIME ERROR | 0.01 s | details |
| #5 | RUNTIME ERROR | 0.01 s | details |
| #6 | RUNTIME ERROR | 0.01 s | details |
| #7 | RUNTIME ERROR | 0.01 s | details |
| #8 | RUNTIME ERROR | 0.01 s | details |
| #9 | RUNTIME ERROR | 0.01 s | details |
| #10 | RUNTIME ERROR | 0.01 s | details |
| #11 | RUNTIME ERROR | 0.01 s | details |
| #12 | WRONG ANSWER | 0.01 s | details |
| #13 | ACCEPTED | 0.01 s | details |
| #14 | WRONG ANSWER | 0.00 s | details |
| #15 | ACCEPTED | 0.01 s | details |
Compiler report
input/code.cpp: In function 'int main()':
input/code.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", input);
~~~~~^~~~~~~~~~~~~Code
#include <cstdio>
#include <cstring>
//#include <algorithm>
const int maxn = 20010;
int A[maxn], B[maxn], C[maxn], D[maxn], *sa = D + 1, *rank, *height;
void sortAndRank(int *a1, int *a2, int n, int &m, int j) {
int i; for (i = 0; i <=m; i++) C[i] =0;
for(i = 0; i < n; i ++) C[a1[i]] ++;
for(i = 1; i <=m; i ++) C[i] += C[i-1];
for(i = n-1; i >= 0; i --) sa[--C[a1[a2[i]]]] = a2[i];
a2[sa[0]] = m = 0;
for(i = 1; i < n; i ++)
a2[sa[i]] = a1[sa[i-1]]==a1[sa[i]] && a1[sa[i-1]+j]==a1[sa[i]+j] ? m : ++ m;
}
void da(char*str, int n, int m) {
int *a1 = A, *a2 = B, *tmp; int i, j, p;
for(i = 0; i < n; i ++) { a1[i] = i; a2[i] = str[i]; }
a1[n] = a2[n] = -1;
sortAndRank(a2, a1, n, m, 0);
for(j = 1; m < n-1; j <<= 1) {
p = 0;
for(i = n-j; i < n; i ++) a2[p ++] = i;
for(i= 0; i < n; i ++) if(sa[i]>=j) a2[p ++] = sa[i]-j;
sortAndRank(a1, a2, n, m, j);
tmp = a1; a1 = a2; a2 = tmp;
} rank = a1; height = a2;
}
void calHeight(char *str, int n) {
int i, j, k;
sa[-1] = n;
for(height[0] = k = i = 0; i < n; i ++) {
for(k ? k-- : 0, j = sa[rank[i]-1]; str[i+k]==str[j+k]; k++);
height[rank[i]] = k;
}
}
char input[maxn];
int main()
{
scanf("%s", input);
int n = strlen(input);
da(input, n, 300);
calHeight(input, n);
int mx = -1;
int res = 0;
for (int i = 1; i < n; i++)
{
if (mx < height[i])
{
mx = height[i];
res = i;
}
}
//printf("%d\n", mx);
//for (int i = 0; i < 2* n; i++)
//{
// printf("%s\n", arr + ar[i]);
//}
printf("%s\n", input + res);
return 0;
}Test details
Test 1
Verdict: WRONG ANSWER
| input |
|---|
| abcdabcdabcd |
| correct output |
|---|
| abcdabcd |
| user output |
|---|
| cdabcdabcd |
Test 2
Verdict: WRONG ANSWER
| input |
|---|
| abcdefghijklmnopqrstuvwxyz |
| correct output |
|---|
| (empty) |
| user output |
|---|
| bcdefghijklmnopqrstuvwxyz |
Test 3
Verdict: RUNTIME ERROR
| input |
|---|
| yypqtdfbwzpfwsmjjagdjpfyqnyspk... |
| correct output |
|---|
| cqkgus |
| user output |
|---|
| (empty) |
Test 4
Verdict: RUNTIME ERROR
| input |
|---|
| zwnqhornqkcmioyxxtkkwrbkorncjh... |
| correct output |
|---|
| dywyvkf |
| user output |
|---|
| (empty) |
Test 5
Verdict: RUNTIME ERROR
| input |
|---|
| fhnnpfcbnpnsigmvmklzvfluwvypyb... |
| correct output |
|---|
| asjzge |
| user output |
|---|
| (empty) |
Test 6
Verdict: RUNTIME ERROR
| input |
|---|
| daqyvtkjopactcbkghijgrpjghmefa... |
| correct output |
|---|
| sowvwyy |
| user output |
|---|
| (empty) |
Test 7
Verdict: RUNTIME ERROR
| input |
|---|
| ksdohlhpsupwqhoditrhvbansccnnh... |
| correct output |
|---|
| devycn |
| user output |
|---|
| (empty) |
Test 8
Verdict: RUNTIME ERROR
| input |
|---|
| edhikrxqidgjpxnyytsfzylndslhyu... |
| correct output |
|---|
| brmnvr |
| user output |
|---|
| (empty) |
Test 9
Verdict: RUNTIME ERROR
| input |
|---|
| hutihnlmghdovkmbelctafdqhldiyl... |
| correct output |
|---|
| bbzhpo |
| user output |
|---|
| (empty) |
Test 10
Verdict: RUNTIME ERROR
| input |
|---|
| ttyameoijyqaxrkvfqkxgrwigmalxw... |
| correct output |
|---|
| cbahwtz |
| user output |
|---|
| (empty) |
Test 11
Verdict: RUNTIME ERROR
| input |
|---|
| aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
| correct output |
|---|
| aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
| user output |
|---|
| (empty) |
Test 12
Verdict: WRONG ANSWER
| input |
|---|
| a |
| correct output |
|---|
| (empty) |
| user output |
|---|
| a |
Test 13
Verdict: ACCEPTED
| input |
|---|
| aa |
| correct output |
|---|
| a |
| user output |
|---|
| a |
Test 14
Verdict: WRONG ANSWER
| input |
|---|
| ab |
| correct output |
|---|
| (empty) |
| user output |
|---|
| b |
Test 15
Verdict: ACCEPTED
| input |
|---|
| zz |
| correct output |
|---|
| z |
| user output |
|---|
| z |
