Cod sursa(job #18974)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 18 februarie 2007 15:55:32
Problema Reguli Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <stdio.h>

#define MAXN 500005

int N;
long long x[MAXN], s[MAXN];
int p[MAXN];

void prefix()
{
	int i, k = 0;
	p[1] = 0;
	for (i = 2; i < N; i++)
	{
		for (; (k > 0) && (s[k + 1] != s[i]); )
			k = p[k];
		if (s[k + 1] == s[i])
			k++;
		p[i] = k;
	}
}

void kmp()
{
	int i, k = 0;
	for (i = 1; i - N + 1 < N; i++)
	{
		for (; (k > 0) && (i < N && s[k + 1] != s[i]); )
			k = p[k];

		if (i >= N || s[k + 1] == s[i])
			k++;

		if (k == N - 1)
		{
			k = p[k];
			if (i != N - 1)
			{
				printf("%d\n", i - N + 1);
				for (k = 1; k <= i - N + 1; k++)
					printf("%lld\n", s[k]);
				return;
			}
		}
	}
}

int main()
{
	freopen("reguli.in", "rt", stdin);
	freopen("reguli.out", "wt", stdout);
	scanf("%d", &N);
	int i;
	for (i = 0; i < N; i++)
		scanf("%lld", x + i);

	for (i = 1; i < N; i++)
		s[i] = x[i] - x[i - 1];
	
	prefix();
	kmp();
	return 0;
}