Variations of Forward-SBNDM.
Hannu Peltola, Jorma Tarhio · 2011
Abstract. Forward-SBNDM is a recently introduced variation of the BNDM algo-rithm for exact string matching. Forward-SBNDM reads a text character following an alignment of the pattern. We present a generalization of this lookahead idea and apply it to SBNDMq for q ≥ 3. As a result we get several new variations of SBNDMq. We introduce a greedy skip loop for SBNDM2. In addition, we tune up our algorithms and the reference algorithms with 2-byte read. According to our experiments, the best of the new variations are in several cases faster than the winners of recent algorithm comparisons.