Cod sursă (job #142526)

#include<cstdio>
#include<cstring>
using namespace std;
char str[500005];
int pi[500005];
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;
}