Pagini recente » Cod sursa (job #1255969) | Cod sursa (job #1215056) | Cod sursa (job #1837667) | Profil alexghita | Cod sursa (job #478546)
Cod sursa(job #478546)
#include<stdio.h>
#include<string.h>
long *a, *p, n, length = 0;
void prefix(){
long k = -1;
p[0] = -1;
for(long i=1; i<n; i++) {
while(k >= 0 && a[i] != a[k+1])
k = p[k];
if(a[k+1] == a[i]) ++k;
p[i] = k;
}
}
void match(long l){
long m = 0, c = n - n%l;
long q = -1;
for(long i=0; i<c; i++){
while(q+1 == l || (q >= 0 && a[q+1] != a[i]))
q = p[q];
if(a[q+1] == a[i]) ++q;
if(q == l - 1) ++m;
}
long index = 0;
if(m == n / l){
for(long i = c; i<n; i++, index++)
if(a[index] != a[i]) return;
length = l;
}
}
void solve(){
for(long i=1; i<n; i++)
a[i-1] = a[i] - a[i-1];
--n;
length = n;
prefix();
for(long i=1; i<n; i++)
if(a[i] == a[0]) {
match(i);
if(length < n) return;
}
}
void read(){
FILE *ifile;
ifile = fopen("reguli.in", "r");
fscanf(ifile, "%li", &n);
a = new long[n];
p = new long[n-1];
for(long i=0; i<n; i++)
fscanf(ifile, "%li", &a[i]);
fclose(ifile);
}
void write(){
FILE *ofile;
ofile = fopen("reguli.out", "w");
fprintf(ofile, "%li\n", length);
for(int i=0; i<length; i++)
fprintf(ofile, "%li\n", a[i]);
fclose(ofile);
}
int main()
{
read();
solve();
write();
return 0;
}