Cod sursă (job #438518)

#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);
  int x=q[n-1],i=n-1;
  while(x==q[i] && x>0){
    x--;
    i--;
  }
  for(int j=0; j<=i; j++)
    fputc(s[j],fout);
  fclose(fin);
  fclose(fout);
  return 0;
}