Cod sursă (job #97844)

#include <cstdio>
#include <cstring>

#define Nmax 500000 + 10

using namespace std;

int n;
int p[Nmax];
char s[Nmax];

void prefix()
{
    int q=0; p[1]=0;

    for (int i=2;i<=n;++i)
    {
        while (q && s[q+1]!=s[i])
            q=p[q];

        if (s[q+1]==s[i])
            ++q;

        p[i]=q;
    }
}

int main()
{
    freopen("bart.in","r",stdin);
    freopen("bart.out","w",stdout);

    gets(s+1); n=strlen(s+1);

    prefix();

    if (!p[n]) puts(s+1);
    else
    {
        for (int i=1;i<=n-p[n];++i)
         printf("%c", s[i]);
    }

    return 0;
}