Tuning SBNDM2 Algorithm For Exact Pattern Matching

Abstract

Pattern matching algorithms are very important in different areas of science. The SBNDM2 algorithm simulates a non-deterministic suffix automaton for the reverse of pattern <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$P$</tex> with the bit-parallelism technique: at the beginning of each alignment, unlike the original BNDM algorithm, it reads a q-gram, i.e., the rightmost q characters in the current window of T with <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathrm{q}=2$</tex>. The objective of this paper was to introduce a tuning of the SBNDM2 algorithm, in the innermost loop specifically. Experimental results showed better running times for this variation.