Pagini recente » Cod sursa (job #3163853) | Cod sursa (job #22595)
Cod sursa(job #22595)
#include<iostream>
#include<fstream>
#define inputfile "reguli.in"
#define outputfile "reguli.out"
const int NMAX = 50000;
using namespace std;
void ReadData(int a[NMAX], int &N) {
ifstream from(inputfile);
from>>N;
for (int i = 0; i<N; i++)
from>>a[i];
for (int i = N-1; i>0; i--)
a[i] -= a[i-1];
N--;
}
void FindMinSubstr(int a[NMAX], int N) {
int p[NMAX];
p[1] = 0;
int k = 0;
int min = 0;
for (int q = 2; q<=N; q++) {
while ( (k > 0) && ( a[k+1] != a[q])) {
min = q - k;
k = p[k];
}
if ( a[k+1] == a[q])
k++;
p[q] = k;
if (k == 0) min = q - p[q];
}
ofstream to(outputfile);
to<<min<<'\n';
for (int i = 1; i<=min; i++) to<<a[i]<<'\n';
}
int main() {
int a[NMAX];
int N;
ReadData(a,N);
// for (int i = 1; i<=N; i++) cout<<a[i]<<' '; cout<<'\n';
FindMinSubstr(a,N);
}