Cod sursă (job #443934)

#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, 500001);
    l = strlen(S);
    int q = -1;
    p[0] = 0;
    for(int i = 1;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 = 0;i < l - p[l - 1] - 1;i++)
        out << S[i];
    return 0;
}