Cod sursa(job #478543)

Utilizator Programmer01Mierla Laurentiu Marian Programmer01 Data 19 august 2010 03:43:52
Problema Reguli Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include<stdio.h>
#include<string.h>

long *a, *p,  n, length = 0;

void prefix(){
	int k = -1;
	p[0] = -1;
	for(int i=1; i<n; i++) {
		while(k >= 0 && a[i] != a[k+1])
			k = p[k];
		if(a[k+1] == a[i]) ++k;
		p[i] = k;
	}
}


void match(long l){
	long m = 0, c = n - n%l;
	long q = -1;
	for(int i=0; i<c; i++){
		while(q+1 == l || (q >= 0 && a[q+1] != a[i]))
			q = p[q];
		if(a[q+1] == a[i]) ++q;
		if(q == l - 1) ++m;
	}
	
	long index = 0;
	if(m == n / l){
		for(int i = c; i<n; i++, index++)
			if(a[index] != a[i]) return;
		
		length = l;
	}
}

void solve(){
	for(int i=1; i<n; i++)
		a[i-1] = a[i] - a[i-1];
	--n;
	
	length = 0;
	prefix();
	
	for(int i=1; i<n; i++)
		if(a[i] == a[0]) {
			match(i);
			if(length > 0) return;
		}
}

void read(){
	FILE *ifile;
	
	ifile = fopen("reguli.in", "r");
	fscanf(ifile, "%li", &n);
	
	a = new long[n];
	p = new long[n-1];
	for(int i=0; i<n; i++)
		fscanf(ifile, "%li", &a[i]);

	fclose(ifile);
}

void write(){
	FILE *ofile;

	ofile = fopen("reguli.out", "w");
	fprintf(ofile, "%li\n", length);
	
	for(int i=0; i<length; i++)
		fprintf(ofile, "%li\n", a[i]);
	fclose(ofile);
}


int main()
{
	read();
	solve();
	write();
	return 0;
}