Pagini recente » Cod sursa (job #1489674) | Cod sursa (job #661663) | Cod sursa (job #716830) | Cod sursa (job #1085805) | Cod sursa (job #2034869)
//KMP
#include<fstream>
using namespace std;
ifstream fi("reguli.in");
ofstream fo("reguli.out");
int n,i,S[500001],k;
long long A[500001],pre,x;
int main()
{
fi>>n;
fi>>pre;
for(i=1; i<=n; i++)
{
fi>>x;
A[i]=x-pre;
pre=x;
}
S[0]=-1;
S[1]=0;
for(i=1; i<n; i++)
{
k=i-1;
while(S[k]!=-1 && A[S[k]+1]!=A[i])
k=S[k];
if(S[k]==-1)
S[i]=0;
else
S[i]=S[k]+1;
}
//nr de perioade este egal cu distanta dintre ultimul lemming
//si cel mai din dreapta lemming ramas in viata in cazul in care
//ultimul cde in groapa
fo<<n-1-S[n-1]<<"\n";
for(i=1; i<=n-1-S[n-1]; i++)
fo<<A[i]<<"\n";
fi.close();
fo.close();
return 0;
}