Cod sursă (job #584816)

#include <bits/stdc++.h>

using namespace std;

ifstream fin("bart.in");
ofstream fout("bart.out");

vector<int> preffix_function(const string &A) {
    vector<int> pi(A.size());
    int N = A.size() - 1;
    for(int i = 2, q = 0; i <= N; ++i) {
        while(q && A[q + 1] != A[i])
            q = pi[q];
        if(A[q + 1] == A[i])
            ++q;
        pi[i] = q;
    }
    return pi;
}

int main() {
    string s;
    fin >> s;
    s = '0' + s;
    vector<int> pi = preffix_function(s);
    int N = s.size() - 1;
    for(int i = 1; i <= N - pi[N]; ++i)
        fout << s[i];
}