Cod sursă (job #308418)

#include <bits/stdc++.h>

using namespace std;

int p[500010];
char s[500010];

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