code

Forward Simplified Backward Nondeterministic DAWG Matching

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