Pagini recente » Istoria paginii utilizator/niculasuditum | Cod sursa (job #180166) | Cod sursa (job #226274) | Cod sursa (job #556064) | Cod sursa (job #478540)
Cod sursa(job #478540)
#include<stdio.h>
#include<string.h>
long *a, *p, n, length;
void prefix(){
int k = -1;
p[0] = -1;
for(int 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(int 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(int i = c; i<n; i++, index++)
if(a[index] != a[i]) return;
length = l;
}
}
void solve(){
for(int i=1; i<n; i++)
a[i-1] = a[i] - a[i-1];
--n;
length = n;
prefix();
for(int i=n-1; i>=1; i--)
if(a[i] == a[0]) match(i);
prefix();
}
void read(){
FILE *ifile;
ifile = fopen("reguli.in", "r");
fscanf(ifile, "%li", &n);
a = new long[n];
p = new long[n-1];
for(int 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;
}