Next: Backward Oracle Matching algorithm Up: ESMAJ Prev: Forward Dawg Matching algorithm

Backward Nondeterministic Dawg Matching algorithm

Main features
• variant of the Reverse Factor algorithm;
• uses bit-parallelism simulation of the suffix automaton of xR;
• efficient if the pattern length is no longer than the memory-word size of the machine;
Description

The BNDM algorithm uses a table B which, for each character c, stores a bit mask. The mask in Bc is set if and only if xi=c.

The search state is kept in a word d=dm-1 .. d0, where the pattern length m is less than or equal to the machine word size.

The bit di at iteration k is set if an only if x[m-i .. m-1-i+k]=y[j+m-k .. j+m-1]. At iteration 0, d is set to 1m-1. The formula to update d follows d'= (d & B[yj]) << 1.

There is a match if and only if, after iteration m, it holds dm-1=1.

Whenever dm-1=1, the algorithm has matched a prefix of the pattern in the current window position j. The longuest prefix matched gives the shift to the next position.

The C code
```void BNDM(char *x, int m, char *y, int n) {
int B[ASIZE];
int i, j, s, d, last;
if (m > WORD_SIZE)
error("BNDM");

/* Pre processing */
memset(B,0,ASIZE*sizeof(int));
s=1;
for (i=m-1; i>=0; i--){
B[x[i]] |= s;
s <<= 1;
}

/* Searching phase */
j=0;
while (j <= n-m){
i=m-1; last=m;
d = ~0;
while (i>=0 && d!=0) {
d &= B[y[j+i]];
i--;
if (d != 0){
if (i >= 0)
last = i+1;
else
OUTPUT(j);
}
d <<= 1;
}
j += last;
}
}

```
The example

Sorry the new example is not ready... See the Java applet.

References
• NAVARRO G., RAFFINOT M., 1998. A Bit-Parallel Approach to Suffix Automata: Fast Extended String Matching, In Proceedings of the 9th Annual Symposium on Combinatorial Pattern Matching, Lecture Notes in Computer Science 1448, Springer-Verlag, Berlin, 14-31.

Next: Backward Oracle Matching algorithm Up: ESMAJ Prev: Forward Dawg Matching algorithm

e-mails: {Christian.Charras, Thierry.Lecroq }@laposte.net
Tue Jan 14 15:03:31 MET 1999