Cod sursă (job #416526)

#include <bits/stdc++.h>
using namespace std;
int i, cnt, KMP[500005];
char str[500005];
int main()
{
    freopen("bart.in", "r", stdin);
    freopen("bart.out", "w", stdout);
    cin >> (str + 1);
    for(i = 2; i <= strlen(str + 1); i++) {
        while(cnt > 0 && str[i] != str[cnt + 1]) cnt = KMP[cnt];
        if(str[i] == str[cnt + 1]) cnt++;
        KMP[i] = cnt;
    }
    for(i = 1; i <= strlen(str + 1) - KMP[strlen(str + 1)]; i++) cout << str[i];
    return 0;
}