code

Genomic Rapid Algofor String Pattern Matching

The Genomic Rapid Algofor String Pattern Matching algorithm
graspm.c

typedef struct GRASPmList {
   int k;
   struct GRASPmList *next;
} GList;

void ADD_LIST(GList **l, int e)  {
   GList *t = (GList *)malloc(sizeof(GList));
   t->k = e;
   t->next = *l;
   *l = t;
}

int search(unsigned char *p, int m, unsigned char *t, int n) {
   GList *pos, *z[SIGMA];
   int i,j,k,count,first, hbc[SIGMA];

   /* Preprocessing of the list */
   for (i=0; i<SIGMA; i++) z[i]=NULL;
   if (p[0] == p[m-1]) for (i=0; i<SIGMA; i++) ADD_LIST(&z[i], 0);
   for (i=0; i<m-1;i++) if (p[i+1] == p[m-1]) ADD_LIST(&z[p[i]],(i+1));
   /* Preprocessing of horspool bc */    
   for (i=0;i<SIGMA;i++) hbc[i]=m;
   for (i=0;i<m;i++) hbc[p[i]]=m-i-1;
   for (i=0;i<m;i++) t[n+i]=p[i];

   /* searching */
   count = 0;
   j = m-1;
   while (j<n) {
      while (k=hbc[t[j]]) j += k; {
         pos = z[t[j-1]];
         while(pos!=NULL) { 
            k = pos->k;
            i = 0; first = j-k;                 
            while(i<m && p[i]==t[first+i]) i++;
            if (i==m && first<=n-m) count++;
            pos = pos->next;
         }
      }
      j+=m;
   }
   return count;
}