code

Forward Simplified Backward Nondeterministic DAWG Matching

The Forward Simplified Backward Nondeterministic DAWG Matching algorithm
fsbndm-w2.c

int search(unsigned char *x, int m, unsigned char *y, int n) {
   unsigned int B[SIGMA],W[SIGMA], d, set, hbcr[SIGMA], hbcl[SIGMA];
   int i, j,s1,s2, pos, mm1, mp1, count;

   /* Preprocessing */
int plen = m;
if (m>31) m=31;
   count = 0;
   mm1 = m - 1;
   mp1 = m + 1;
   set = 1;
   for (i=0; i<SIGMA; i++)   B[i]=W[i]=set;
   for (i = 0; i < m; ++i) {
     B[x[i]] |= (1<<(m-i));
     W[x[m-1-i]] |= (1<<(m-i));
   }

   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 */
   s1 = mm1; s2=n-plen;
   while (s1 <= s2+mm1) {
      while (s1<=s2+mm1 && ( d = (((B[y[s1+1]]<<1)&B[y[s1]]) | ((W[y[s2-1]]<<1)&W[y[s2]]) )) == 0) { 
        s1 += hbcr[y[s1+m]];
        s2 -= hbcl[y[s2-m]];
      }
pos = s1;
while (d=(d+d)& (B[y[s1-1]]|W[y[s2+1]])) { --s1; ++s2; }
      s1 += mm1;
      s2 -= mm1;
      if (s1==pos) {
i=0; j=s1-mm1;
while(i<plen && x[i]==y[j+i]) i++;
if (i==plen && s1<=s2+mm1) count++;
i=0;
while(i<plen && x[i]==y[s2+i]) i++;
if (i==plen && s1<s2+mm1) count++;
         ++s1;
         --s2;
      }
}
   return count;
}