Cod sursă (job #443939)

#include <bits/stdc++.h>

using namespace std;
ifstream in("bart.in");
ofstream out("bart.out");
char S[500001];
int l, p[500001], x;
int main()
{
    in.getline((S + 1), 500001);
    l = strlen(S + 1);
    int q = 0;
    p[1] = 0;
    for(int i = 2;i <= l;i++)
    {
        while(S[i] != S[q + 1] && q > 0) q = p[q];
        if(S[i] == S[q + 1])q++;
        p[i] = q;
    }
    for(int i = 1;i <= l - p[l];i++)
        out << S[i];
    return 0;
}