Cod sursă (job #95538)

#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 poz = 0, i;
	bool corect = false;
	for (i = 0; i <= n; i++)
	{
		if (pref[i] == pref[i-1] + 1 && corect == false)
		{
			poz = i - 1;
			corect = true;
		}
		
		if (pref[i] != pref[i-1] + 1)
			corect = false;
		
	}
	for (i = 0; i <= poz; i++)
	{
		fprintf(out, "%c", s[i]);
	}
	return 0;
}