Cod sursă (job #93121)

#include <stdio.h>
#include <string.h>
#define MAX 500000

char s[MAX + 2]; // \n + \0
int pi[MAX + 1];

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

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

	// Algoritmul de prefix
	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;
	}

	// Truncherea sirului la primele N - pi[N - 1] caractere
	s[N - pi[N - 1]] = '\0';
    fputs(s, fout);

    fclose(fin);
    fclose(fout);
    return 0;
}