Cod sursă (job #416527)

#include <fstream>
#include <string.h>
using namespace std;
ifstream fin ("bart.in");
ofstream fout ("bart.out");
int i, cnt, KMP[500005];
char str[500005];
int main()
{
    fin >> (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++) fout << str[i];
    return 0;
}