algorithm - Program Bugs with large sequences (C) -

i trying code waterman algorithm in c. when length of sequence exceeds 35 program lags. have no idea start looking, tried got nothing worked out.

here's code:

#include <stdio.h> #include <stdlib.h> #include <time.h>  // max function prototype. int maxfunction(int, int);  // prototype of random sequences generator function. void gen_random(char *, const int);  int main(int argc, char *argv[]) {         // looping variable , sequences.     int = 0, j = 0, k = 0;     char *x, *y;     int length1, length2;      // time variables.     time_t beginning_time, end_time;      // getting lengths of sequences     printf("please provide length of first sequence\n");     scanf("%d", &length1);      printf("please provide length of second sequence\n");     scanf("%d", &length2);      x = (char*)malloc(sizeof(char) * length1);     y = (char*)malloc(sizeof(char) * length2);      int m = length1 + 1;     int n = length2 + 1;     int l[m][n];     int backtracking[m + n];      gen_random(x, length1);     gen_random(y, length2);      printf("first sequence\n");     (i = 0; < length1; i++) {         printf("%c\n", x[i]);     }     printf("\nsecond sequence\n");     (i = 0; < length2; i++) {         printf("%c\n", y[i]);     }      // time calculation beginning.     beginning_time = clock();      // main part--core of algorithm.     (i = 0; <= m; i++) {         (j = 0; j <= n; j++) {             if (i == 0 || j == 0) {                 l[i][j] = 0;             } else             if (x[i-1] == y[j-1]) {                 l[i][j] = l[i-1][j-1] + 1;                 backtracking[i] = l[i-1][j-1];             } else {                 l[i][j] = maxfunction(l[i-1][j], l[i][j-1]);                 backtracking[i] = maxfunction(l[i-1][j], l[i][j-1]);             }         }     }      // end time calculation.     end_time = clock();      (i = 0; < m; i++) {         printf(" ( ");         (j = 0; j < n; j++) {             printf("%d ", l[i][j]);         }         printf(")\n");     }      // printing out result of backtracking.     printf("\n");     (k = 0; k < m; k++) {         printf("%d\n", backtracking[k]);     }      printf("consumed time: %lf", (double)(end_time - beginning_time));     return 0; }  // max function. int maxfunction(int a, int b) {     if (a > b) {         return a;     } else {         return b;     } }  // random sequence generator function. void gen_random(char *s, const int len) {     int = 0;     static const char alphanum[] = "acgt";      (i = 0; < len; ++i) {         s[i] = alphanum[rand() % (sizeof(alphanum) - 1)];     }     s[len] = 0; } 

since null terminate sequence in gen_random s[len] = 0;, should allocate 1 more byte each sequence:

x = malloc(sizeof(*x) * (length1 + 1)); y = malloc(sizeof(*y) * (length2 + 1)); 

but since define variable length arrays other variables, might define these as:

char x[length1 + 1], y[length2 + 1]; 

yet else causing crash on laptop: nested loops iterate i = 0 i <= m, , j = 0 j <= n. that's 1 step many, index out of bounds l.

here corrected version:

for (i = 0; < m; i++) {     (j = 0; j < n; j++) { 

the resulting code executes quickly, complexity o(m*n) in both time , space, m , n reasonably small @ 35. runs in less 50ms 1000 x 1000.

whether implements smith-waterman's algorithm correctly question.