Cod sursă (job #93850)

#include<stdio.h>
using namespace std;
const int L = 500002;
char s[L];
int pref[L];
int main ()
{
	FILE *in, *out;
	in = fopen ("bart.in", "r");
	out = fopen ("bart.out", "w");
	int n = -1;
	char x;
	x = fgetc (in);
	while (x != '\n')
	{
		s[++n] = x;
		x = fgetc(in);
	}
	int q = 0, k = 0;
	pref[q] = 0;
	int max = -1;
	for (q = 1; q <= n; q++)
	{
		while (k > 0 && s[q] != s[k])
			k = pref[k - 1];
		if (s[k] == s[q])
			k++;
		pref[q] = k;
		if (k > max)
			max = k;
	}
	int i;
    for(i=0;i<=n-pref[n];i++)
        fprintf(out,"%c",s[i]);
	return 0;
}