Cod sursa(job #2747686)

Utilizator AndreiCroitoruAndrei Croitoru AndreiCroitoru Data 29 aprilie 2021 15:45:35
Problema Reguli Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <bits/stdc++.h>
using namespace std;
int v[500001];
int pi[500001];
int main()
{
	ifstream cin("reguli.in");
	ofstream cout("reguli.out");
	int n;
	cin>>n;
	int aux=0;
	cin>>aux;
	int nr,k=0;
	for(int i=2;i<=n;i++)
	{
		cin>>nr;
		v[++k]=nr-aux;
		aux=nr;
	}
	/// avem un vector cu diferente si trb sa cautam un subtring a.i. sa putem forma sirul ala mare cu el... partea grea e ca pot sa raman si bugati nenorocite
	
	/// update e ezzzz faci daor o functie de prefix wtf
	
	int q=0;
	pi[1]=0;
	for(int i=2;i<=k;i++)
	{
		while((q>0) and v[q+1]!=v[i])
		q=pi[q];
		if(v[q+1]==v[i])
		{
			q=q+1;
		}
		pi[i]=q;
	}
	cout<<k-pi[n]<<'\n';
	for(int i=1;i<=k-pi[k];i++)
	{
		cout<<v[i]<<'\n';
	}
}