code

Simplified Backward Nondeterministic DAWG Matching

The Simplified Backward Nondeterministic DAWG Matching algorithm
sbndm-w2.c


int search(unsigned char *x, int m, unsigned char *y, int n) {
   int B[SIGMA], W[SIGMA], hbcr[SIGMA], hbcl[SIGMA], PR[SIGMA];
   int i, j, s1,s2, h, f,d, z,first, count, stop;
   int plen = m;
   if (m>32) m=32;
   int m1 = m-1;
   int mp1 =  m+1;   

   /* Pre processing*/ 
   for (i=0; i<SIGMA; i++) B[i]=W[i]=0;
   j=1;
   f=1<<(m-1);
   for (i=m-1; i>=0; i--) {
B[x[i]] |= j;
W[x[i]] |= f;
j <<= 1;
      f >>= 1;
   }

for (i=0;i<SIGMA;i++)   hbcr[i]=hbcl[i]=2*m;
   for (i=0;i<m;i++) {
       hbcr[x[i]]=(2*m)-i-1;
       hbcl[x[m-1-i]]=(2*m)-i-1;
   }

   /* Searching phase */
   s1=m1; s2=n-m; count=0;
   while (s1 <= s2+m1){
         while ((d = (B[y[s1]]|W[y[s2]])) == 0) {
         s1 += hbcr[y[s1+m]];
         s2 -= hbcl[y[s2-m]];
      }
      first=s1-m1; 
do {
         d = (d<<1) & (B[y[--s1]]|W[y[++s2]]);
} while (d);
      if (s1<first) {
s1++;
s2--;
i=0;
while(i<plen && x[i]==y[s1+i]) i++;
if (i==plen && s1+m1<s2) count++;
i=0;
while(i<plen && x[i]==y[s2-m1+i]) i++;
if (i==plen && s1+m1<=s2) count++;
      }
      s1+=m;
s2-=m;
   }
return count;
}