CSES - E4590 2016 6 - Results
Submission details
Task:Period
Sender:Ollie
Submission time:2016-10-22 22:07:07 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.09 sdetails
#2ACCEPTED0.08 sdetails
#3ACCEPTED0.10 sdetails
#4ACCEPTED0.08 sdetails
#5ACCEPTED0.10 sdetails
#6ACCEPTED0.09 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:22:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<za.size();i++) {
                         ^
input/code.cpp:23:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(za[i] == za.size()-i) {
                           ^

Code

#include <bits/stdc++.h>

using namespace std;

vector<int> z(string s) {
  int n = s.size();
  vector<int> z(n);
  int x = 0, y = 0;
  for(int i=1;i<n;i++) {
    z[i] = max(0,min(z[i-x],y-i+1));
    while(i+z[i]<n&&s[z[i]]==s[i+z[i]]) {
      x = i; y = i+z[i]; z[i]++;
    }
  }
  return z;
}

int main() {
  string s;
  cin >> s;
  auto za = z(s);
  for(int i=1;i<za.size();i++) {
    if(za[i] == za.size()-i) {
      cout << s.substr(0,i) << endl;
      return 0;
    }
  }
  cout<<s<<endl;
  return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

correct output
a

user output
a

Test 2

Verdict: ACCEPTED

input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

correct output
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

user output
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

Test 3

Verdict: ACCEPTED

input
nabvmrnenabvmrnenabvmrnenabvmr...

correct output
nabvmrne

user output
nabvmrne

Test 4

Verdict: ACCEPTED

input
fwqrbqnmobvwslpyfrlkrfwluaxyzk...

correct output
fwqrbqnmobvwslpyfrlkrfwluaxyzk...

user output
fwqrbqnmobvwslpyfrlkrfwluaxyzk...

Test 5

Verdict: ACCEPTED

input
ohicwwkhdoesqvsyemhdhubpvmqkre...

correct output
ohicwwkhdoesqvsyemhdhubpvmqkre...

user output
ohicwwkhdoesqvsyemhdhubpvmqkre...

Test 6

Verdict: ACCEPTED

input
gqzzocfzbuvfovbvamyflvcuuajzgu...

correct output
gqzzocfzbuvfovbvamyflvcuuajzgu...

user output
gqzzocfzbuvfovbvamyflvcuuajzgu...