Submission details
Task:Repeating substring
Sender:sfjiang
Submission time:2020-09-26 14:20:04 +0300
Language:C++ (C++11)
Status:READY
Result:
Test results
testverdicttime
#10.01 sdetails
#20.00 sdetails
#30.01 sdetails
#40.01 sdetails
#50.01 sdetails
#60.01 sdetails
#70.01 sdetails
#80.01 sdetails
#90.01 sdetails
#100.01 sdetails
#110.01 sdetails
#120.01 sdetails
#13ACCEPTED0.01 sdetails
#140.00 sdetails
#15ACCEPTED0.01 sdetails

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:

input
abcdabcdabcd

correct output
abcdabcd

user output
cdabcdabcd

Test 2

Verdict:

input
abcdefghijklmnopqrstuvwxyz

correct output
(empty)

user output
bcdefghijklmnopqrstuvwxyz

Test 3

Verdict:

input
yypqtdfbwzpfwsmjjagdjpfyqnyspk...

correct output
cqkgus

user output
(empty)

Test 4

Verdict:

input
zwnqhornqkcmioyxxtkkwrbkorncjh...

correct output
dywyvkf

user output
(empty)

Test 5

Verdict:

input
fhnnpfcbnpnsigmvmklzvfluwvypyb...

correct output
asjzge

user output
(empty)

Test 6

Verdict:

input
daqyvtkjopactcbkghijgrpjghmefa...

correct output
sowvwyy

user output
(empty)

Test 7

Verdict:

input
ksdohlhpsupwqhoditrhvbansccnnh...

correct output
devycn

user output
(empty)

Test 8

Verdict:

input
edhikrxqidgjpxnyytsfzylndslhyu...

correct output
brmnvr

user output
(empty)

Test 9

Verdict:

input
hutihnlmghdovkmbelctafdqhldiyl...

correct output
bbzhpo

user output
(empty)

Test 10

Verdict:

input
ttyameoijyqaxrkvfqkxgrwigmalxw...

correct output
cbahwtz

user output
(empty)

Test 11

Verdict:

input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

correct output
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

user output
(empty)

Test 12

Verdict:

input
a

correct output
(empty)

user output
a

Test 13

Verdict: ACCEPTED

input
aa

correct output
a

user output
a

Test 14

Verdict:

input
ab

correct output
(empty)

user output
b

Test 15

Verdict: ACCEPTED

input
zz

correct output
z

user output
z