CSES - E4590 2016 6 - Results
Submission details
Task:Period
Sender:hugues
Submission time:2016-10-24 09:11:26 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.07 sdetails
#2ACCEPTED0.06 sdetails
#30.06 sdetails
#40.05 sdetails
#50.06 sdetails
#60.05 sdetails

Compiler report

input/code.cpp: In function 'void computeZarray(std::string, int*)':
input/code.cpp:10:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < n; ++i) {
                         ^
input/code.cpp:13:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (R < n && str[R - L] == str[R]) R++;
                        ^
input/code.cpp:21:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while (R < n && str[R - L] == str[R]) R++;
                            ^
input/code.cpp: In function 'int main()':
input/code.cpp:46:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (Z[i] == s.length() - i) {
                                          ^

Code

#include <bits/stdc++.h>

using namespace std;


void computeZarray(string str, int *Z) {
    size_t n = str.length();
    int L, R, k;
    L = R = 0;
    for (int i = 1; i < n; ++i) {
        if (i > R) {
            L = R = i;
            while (R < n && str[R - L] == str[R]) R++;
            Z[i] = R - L;
            R--;
        } else {
            k = i - L;
            if (Z[k] < R - i + 1) Z[i] = Z[k];
            else {
                L = i;
                while (R < n && str[R - L] == str[R]) R++;
                Z[i] = R - L;
                R--;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cout.tie(0);

    string s;
    cin >> s;
    bool has_printed = false;

    if (s.length() == 1) {
        cout << s;
        has_printed = true;
    } else {
        int Z[s.length()];
        computeZarray(s, Z);

        for (unsigned long i = 1; i < s.length(); i++) {
            if (Z[i] > 0) {
                if (Z[i] == s.length() - i) {
                    cout << s.substr(0, i);
                    has_printed = true;
                }
                break;
            };
        }
    }
    if(!has_printed) cout << s;
    cout << 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:

input
nabvmrnenabvmrnenabvmrnenabvmr...

correct output
nabvmrne

user output
nabvmrnenabvmrnenabvmrnenabvmr...

Test 4

Verdict:

input
fwqrbqnmobvwslpyfrlkrfwluaxyzk...

correct output
fwqrbqnmobvwslpyfrlkrfwluaxyzk...

user output
fwqrbqnmobvwslpyfrlkrfwluaxyzk...

Test 5

Verdict:

input
ohicwwkhdoesqvsyemhdhubpvmqkre...

correct output
ohicwwkhdoesqvsyemhdhubpvmqkre...

user output
ohicwwkhdoesqvsyemhdhubpvmqkre...

Test 6

Verdict:

input
gqzzocfzbuvfovbvamyflvcuuajzgu...

correct output
gqzzocfzbuvfovbvamyflvcuuajzgu...

user output
gqzzocfzbuvfovbvamyflvcuuajzgu...