root/misc/sequenza.c

/* AlpT
 * Thu Jul 14 01:12:10 CEST 2005
 * Mazara del Vallo
 *
 * sequenza.c:
 * Given a list of numbers separated by a '\n' in stdin, it finds (if any) the
 * cyclic sequences in the list and it prints them:
 * 54 6 9 2 1 9 2 1 54 6 9 2 1 9 2 1 54 6 9 2 1 9 2 1 54 6 9 2 1 9 2 1
 * In the above case the cyclic sequence is:
 * 54 6 9 2 1 9 2 1
 *
 * In the worst case the O-big notation of the algorithm is:
 * O(n + n/2 + n/3 + n/... + n/n), where n is the number of numbers in the
 * list.
 */

#include <stdio.h>

int main()
{
        int n,i, alloced=500, e, o, x;
        int *seq;
        char s[19];

        n=0;
        seq=(int *)malloc(alloced*sizeof(int));
        while(fgets(s, sizeof(s), stdin)) {
                if(s[0] == '\n')
                        continue;
                
                seq[n]=atoi(s);
//              printf("seq[%d]: %d\n", n, seq[n]);
                n++;
                if(n == alloced) {
                        alloced*=2;
                        seq=(int *)realloc(seq, alloced*sizeof(int));
                }
        }

        if(!n)
                goto finish;

        /* 
         * find sequence 
         */

//      printf("n: %d\n",n);
        for(i=1; i <= n/2; i++) {
//              printf("i: %d\n",i);
                o=0;    
                for(e=1; e*i <= n-i; e++) {
//                      printf("e: %d\n",e);
                        for(x=0; x<i; x++) {
//                              printf("x: %d. a:%d, b:%d\n", x,seq[x],seq[x+e*i]);
                                if(seq[x] != seq[x+e*i])
                                        break;
                        }
                        if(x < i) {
                                o=1;
                                break;
                        }
                }

                if(!o) {
                        for(o=0; o < i; o++)
                                printf("%d ", seq[o]);
                        printf("\n");
                }
        }

finish: 
        free(seq);
}