Cod sursă (job #416478)

#include <bits/stdc++.h>

using namespace std;
int n, Max, a[500005];
char s[500005];

int main()
{
    freopen("bart.in", "r", stdin);
    freopen("bart.out", "w", stdout);
    gets(s+1);
    n=strlen(s+1);
    int k=0, q;
    a[1]=0;
    for(q=2; q<=n; q++)
    {
        while(k>0 && s[k+1]!=s[q])
            k = a[k-1];
        if(s[k+1]==s[q])
            k++;
        a[q]=k;
    }
    for(int i=1; i<=n-a[n]; i++)
        printf("%c", s[i]);
    return 0;
}