Cod sursă (job #376666)

#include <fstream>
#include <cstring>

using namespace std;

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

char ch[500005];
int pre[500005];

int main()
{
    in>>(ch+1);
    int p = 0;
    int len = strlen(ch+1);
    for(int i = 2; i <= len; i ++)
    {
        while(p && ch[i] != ch[p + 1])
            p = pre[p];
        if(ch[i] == ch[p + 1])
            p++;
        pre[i] = p;
    }
    for(int i = 1; i <= len - pre[len]; i ++)
        out << ch[i];
    return 0;
}