Cod sursă (job #442968)

#include <bits/stdc++.h>

using namespace std;

ifstream fin("bart.in");
ofstream fout("bart.out");

const int NMAX = 500005;
char c[NMAX];
int p[NMAX];

int main()
{
    fin >> (c+1);
    int n=strlen(c+1),q;
    p[1]=0;
    for(int i=2;i<=n;i++)
    {
        q=p[i-1];
        while(c[q+1]!=c[i] and q!=0)
        {
            q=p[q];
        }
        if(c[q+1]!=c[i]) p[i]=0;
        else p[i]=q+1;
    }
    for(int i=1;i<=n-p[n];i++) fout << c[i];
    return 0;
}