code

Forward Simplified Backward Nondeterministic DAWG Matching

The Forward Simplified Backward Nondeterministic DAWG Matching algorithm
fsbndm-w4.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,s3,s4, 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 */
int q = n/2;
   s1 = mm1; s2=q-m; s3=q; s4=n-plen;
   while (s1 <= s2+mm1 || s3<=s4+mm1) {
      while (( d = (((B[y[s1+1]]<<1)&B[y[s1]]) | ((W[y[s2-1]]<<1)&W[y[s2]]) | ((B[y[s3+1]]<<1)&B[y[s3]]) | ((W[y[s4-1]]<<1)&W[y[s4]]) )) == 0) { 
        s1 += hbcr[y[s1+m]];
        s2 -= hbcl[y[s2-m]];
  s3 += hbcr[y[s3+m]];
  s4 -= hbcl[y[s4-m]];
      }
pos = s1;
while (d=(d+d) & (B[y[s1-1]]|W[y[s2+1]]|B[y[s3-1]]|W[y[s4+1]])) { --s1; ++s2; --s3; ++s4; }
      s1 += mm1;
      s2 -= mm1;
      s3 += mm1;
      s4 -= 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++;
i=0; j=s3-mm1;
while(i<plen && x[i]==y[j+i]) i++;
if (i==plen && s3<=s4+mm1) count++;
i=0;
while(i<plen && x[i]==y[s4+i]) i++;
if (i==plen && s3<s4+mm1) count++;
         ++s1;
         --s2;
         ++s3;
         --s4;
      }
}
   return count;
}