Cod sursa(job #2179224)

Utilizator IulianBobocBoboc Iulian IulianBoboc Data 20 martie 2018 00:37:20
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<fstream>
using namespace std;
#define nMax 500004

long long series[nMax], a[nMax];
int pi[nMax], aLength, seriesLength, K;
void computePrefixFunction(long long pattern[], int patternLength){
	int k = -1;
	pi[0] = -1;
	for(int i = 1; i < patternLength; ++i){
		while( k > -1 && pattern[k+1] != pattern[i]){
			k = pi[k];
		}
		if(pattern[k+1] == pattern[i]){
			k = k + 1;
		}
		pi[i] = k;
	}
}
int main(){

	ifstream fin("reguli.in");
	ofstream fout("reguli.out");
	int N, i;
	fin >> N;

	for(i = 0; i < N; ++i){
		long long number;
		fin >> number;
		series[seriesLength++] = number;
	}

	for(int i = 1; i < seriesLength; ++i){
		a[aLength++] = series[i] - series[i - 1];
	}

	computePrefixFunction(a, aLength);

	K = aLength - pi[aLength - 1] - 1;

	fout << K << "\n";
	for(i = 0; i < K; ++i){
		fout << a[i] << "\n";
	}

	fin.close();
	fout.close();
	return 0;
}