Cod sursă (job #124738)

#include<cstdio>
#include<cstring>
#difine NMAX  500005
using namespace std;
char str[NMAX];
int pi[NMAX];

int main() {
    freopen("bart.in", "r", stdin);
    freopen("bart.out", "w", stdout);
    int i, p, j, len;

    scanf("%s", str + 1);
    len = strlen(str + 1);

    p = 0;
    for(i = 2; i <= len; ++ i) {
        while(p && str[i] != str[p + 1])
            p = pi[p];

        if(str[i] == str[p + 1])
            ++ p;

        pi[i] = p;
    }

    for(j = 1; j <= len - pi[len]; ++ j)
        printf("%c", str[j]);
    printf("\n");
    return 0;
}