Cod sursă (job #438665)

#include <stdio.h>
#include <string.h>
#define MAX 500000
FILE *fin,*fout;
int n,q[MAX];
char s[MAX+1];

void creare_q(int m, char *p){//q[i]=cel mai lung prefix care e si sufix al s[0...i]
  q[0]=0;
  int j=0;
  for(int i=1; i<m; i++){
    while(j>0 && p[i]!=p[j])
      j=q[j-1];
    if(p[i]==p[j])
      j++;
    q[i]=j;
  }
}

int main(){
  fin=fopen("bart.in","r");
  fout=fopen("bart.out","w");

  fscanf(fin,"%s",&s);
  n=strlen(s);
  creare_q(n,s);
  for(int i=0; i<n-q[n-1]; i++)
    fputc(s[i],fout);
  fclose(fin);
  fclose(fout);
  return 0;
}