Cod sursă (job #293474)

#include <stdio.h>

#define MAX_N 500000

int pi[MAX_N];
char s[MAX_N + 2];

int main(void) {
  int q, n, i;

  FILE *f = fopen("bart.in", "r");
  fgets(s, MAX_N + 2, f);
  fclose(f);

  q = pi[0] = 0;
  n = 1;
  while (s[n] != '\n') {
    while ((q > 0) && s[q] != s[n]) {
      q = pi[q - 1];
    }
    if (s[q] == s[n]) {
      ++q;
    }
    pi[n++] = q;
  }

  f = fopen("bart.out", "w");
  for (i = 0; i < n - pi[n - 1]; i++) {
    fputc(s[i], f);
  }
  fprintf(f, "\n");
  fclose(f);

  return 0;
}