Cod sursa(job #578633)

Utilizator avram_florinavram florin constantin avram_florin Data 11 aprilie 2011 13:58:23
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<fstream>
#define LL long long

using namespace std;

const int MaxN = 500005;
const char InFile[] = "reguli.in";
const char OutFile[] = "reguli.out";

LL s[MaxN];
int N,sol,urm[MaxN];

int KMP()
{
	int q,k,T;
	T = N-1;
	k = 0;
	urm[0] = urm[1] = 0;
	for( q = 2 ; q < N ; q++ )
		{
			while( k > 0 && s[q] != s[k+1] )
				k = urm[k];
			if( s[q] == s[k+1] )
				k++;
			if( k && !(q%(q-k)) )
				T = q-k;
		}
	return T;
}

int main()
{
	ifstream f ( InFile );
	ofstream g ( OutFile );
	LL x,y;
	int i;
	f >> N >> x;
	for( i = 1 ; i < N ; i++ )
		{
			f >> y;
			s[i] = y-x;
			x = y;
		}
	int T;
	T = KMP();
	g << T << '\n';
	for( i = 1 ; i <= T ; i++ )
		g << s[i] << '\n';
	f.close();
	g.close();
	return 0;
}