Pagini recente » Cod sursa (job #66658) | Cod sursa (job #1110922) | Cod sursa (job #2976289) | Cod sursa (job #556539) | Cod sursa (job #2179208)
#include<fstream>
using namespace std;
#define nMax 500000
int pi[nMax], series[nMax], a[nMax], aLength, seriesLength, K;
void computePrefixFunction(int 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){
int number;
fin >> number;
series[seriesLength++] = number;
}
for(int i = 1; i < seriesLength; ++i){
a[aLength++] = series[i] - series[i - 1];
}
computePrefixFunction(a, aLength);
for(i = seriesLength - 1; i >= 0; --i){
K = i - pi[i];
if((i + 1) % K == 0){
int q = i;
int pq = pi[q];
while(pq >= 0 && (q + 1) % K == 0){
q = pq;
pq = pi[q];
}
if( pq < 0){
break;
}
}
}
fout << K << "\n";
for(i = 0; i < K; ++i){
fout << a[i] << "\n";
}
fin.close();
fout.close();
return 0;
}