Cod sursă (job #378261)

#include <fstream>
#include <cstring>

using namespace std;

ifstream cin("bart.in");
ofstream cout("bart.out");

char ch[500005];
int prefix[500005];

int main()
{
    cin>>(ch+1);
    int p = 0, cuv = strlen(ch+1);
    for(int i = 2; i <= cuv; i ++)
    {
        while(p && ch[i] != ch[p + 1])
            p = prefix[p];
        if(ch[i] == ch[p + 1])
            p++;
        prefix[i] = p;
    }
    for(int i = 1; i <= cuv - prefix[cuv]; i ++)
        cout << ch[i];
    return 0;
}