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 |