Tuning SBNDM2 Algorithm For Exact Pattern Matching
Jorge Teran Pomier, Lucio Torrico Diaz · 2023
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$P$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$\mathrm{q}=2$. 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.