Cod sursă (job #153231)

#include <stdio.h>
#include <string.h>

#define MAX_N 500000

char s[MAX_N];
int z[MAX_N];

inline int MIN(int A, int B) {
  return A < B ? A : B;
}

int main(void) {
  FILE *f = fopen("bart.in", "r");
  int lo, hi;
  int n;
  int i;

  fscanf(f, "%s", s);
  fclose(f);

  n = strlen(s);
  lo = 0;
  hi = 0;
  for (i = 1; i < n; i++) {
    if (i <= hi) {
      z[i] = MIN(hi - i + 1, z[i - lo]);
    }
    while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
      z[i]++;
    }
    if (i + z[i] - 1 > hi) {
      lo = i;
      hi = i + z[i] - 1;
    }
  }

  i = 1;
  while (i < n && z[i] + i != n) {
    i++;
  }
  s[i] = '\0';
  
  f = fopen("bart.out", "w");
  fputs(s, f);
  fclose(f);
  return 0;
}