Cod sursă (job #206156)

#include <cstdio>
#define MAXN 500000
char v[MAXN+1];
int pi[MAXN+1];
int main(){
    FILE*fi,*fout;
    int n,i,j;
    char a;
    fi=fopen("bart.in" ,"r");
    fout=fopen("bart.out" ,"w");
    a=fgetc(fi);
    n=0;
    while((a>='A'&&a<='Z')||(a>='a'&&a<='z')){
        v[++n]=a;
        a=fgetc(fi);
    }
    pi[1]=0;
    for(i=2;i<=n;i++){
        if(v[i]==v[pi[i-1]+1])
           pi[i]=pi[i-1]+1;
        else{
           j=i-1;
           while(j>1&&v[pi[j]+1]!=v[i])
              j=pi[j];
           pi[i]=pi[j]+1;
           if((j==0||j==1)&&v[1]!=v[i])
               pi[i]=0;
        }
    }
    for(i=1;i<=n-pi[n];i++)
        fprintf(fout,"%c" ,v[i]);
    fclose(fi);
    fclose(fout);
    return 0;
}