Name
  • String
  • Substring
  • Search
Edit

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.


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;

C