Cod sursă (job #442755)

#include<cstdio>
#include<cstring>
using namespace std;

const int NMAX=500005;
char s[NMAX];
int urm[NMAX];

int main(){
    freopen("bart.in","r",stdin);
    freopen("bart.out","w",stdout);
    int n,k=0;
    scanf("%s", s+1);
    n=strlen(s+1);
    for(int i=2;i<=n;i++){
        while(k>0 && s[k+1]!=s[i])
            k=urm[k];
        if(s[k+1]==s[i])
            k++;
        urm[i]=k;
    }
    for(int i=1;i<=n-urm[n];i++)
        printf("%c", s[i]);
    return 0;
}