Prague Stringology Conference 2011
Hannu Peltola and Jorma Tarhio
Variations of Forward-SBNDM
| Abstract: |
| Forward-SBNDM is a recently introduced variation of the BNDM algorithm 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. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |