Cod sursă (job #530894)

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

char s[500001];
int pref[500001];
int main() {
  FILE *fin, *fout;
  int i, lc, n;
  fin=fopen("bart.in","r");
  fout=fopen("bart.out","w");
  fscanf(fin, "%s",&s);
  n=strlen(s);
  for(i=2;i<n;i++) {
    if(i!=0)
      lc=pref[i-1];
    else
      lc=0;
    if(i==1)
      printf("%d ",lc);
    while(lc>0 && s[lc+1]!=s[i])
      lc=pref[lc];
    if(s[lc+1]==s[i])
      lc++;
    pref[i]=lc;
  }
  for(i=0;i<n-pref[n-1]-1;i++)
    fprintf(fout, "%c",s[i]);
  fclose( fin );
  fclose( fout );
  return 0;
}