Cod sursă (job #93058)

#include <stdio.h>
#include <string.h>
#define MAX 500000
char s[MAX+2];
int pi[MAX+1];

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

    int N;
    fgets(s, sizeof(s), fin);
    N = strlen(s) - 1;

    int i, k = 0;
    for (i = 1; i < N; i++) {
        while ((k > 0) && (s[k] != s[i])) {
            k = pi[k - 1];
        }
        if (s[k] == s[i]) {
            k++;
        }
        pi[i] = k;
    }

    s[N - pi[N - 1]] = '\0';
    fputs(s, fout);
    fclose(fin);
    fclose(fout);
    return 0;
}