code

Simplified Backward Nondeterministic DAWG Matching

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


int search(unsigned char *x, int m, unsigned char *y, int n) {
   int B[SIGMA], W[SIGMA], hbcr[SIGMA], hbcl[SIGMA];
   int i, j, s,s1,s2,s3,s4, 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;
   s=1;
   f=1<<(m-1);
   for (i=m-1; i>=0; i--) {
B[x[i]] |= s;
W[x[i]] |= f;
s <<= 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 */
   int q = n/2;
   s1=m-1; s2=q-m; s3 = q; s4=n-m; count=0;
   while (s1<=s2+m1 || s3<=s4+m1){
         while ((d = (B[y[s1]]|W[y[s2]]|B[y[s3]]|W[y[s4]])) == 0) {
         s1 += hbcr[y[s1+m]];
         s2 -= hbcl[y[s2-m]];
         s3 += hbcr[y[s3+m]];
         s4 -= hbcl[y[s4-m]];
      }
      first=s1-m1; 
do d = (d<<1) & (B[y[--s1]]|W[y[++s2]]|B[y[--s3]]|W[y[++s4]]);  while (d);
      if (s1<first) {
s1++;
s2--;
s3++;
s4--;
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++;
i=0;
while(i<plen && x[i]==y[s3+i]) i++;
if (i==plen && s3+m1<s4) count++;
i=0;
while(i<plen && x[i]==y[s4-m1+i]) i++;
if (i==plen && s3+m1<=s4) count++;
      }
      s1+=m;
      s2-=m;
      s3+=m;
      s4-=m;
   }
      return count;
}