Cod sursă (job #416466)

#include <bits/stdc++.h>

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

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