Prague Stringology Conference 2017

Igor O. Zavadskyi

A Family of Exact Pattern Matching Algorithms with Multiple Adjacent Search Windows

A new family of comparison-based exact pattern matching algorithms is presented. They utilize the multi-dimensional arrays in order to process more than one adjacent search window in each iteration of the search loop. This approach leads to a lower average computing time by the cost of space. However, the excessive space consumption can be avoided due to a special technique of replacing a multi-dimensional array with a series of one-dimensional arrays of pointers. The algorithms of this family perform well for short or middle-size patterns, when the shift of a search window by several lengths at once is quite probable. Our algorithms outperform all other known algorithms for some values of pattern length on English text, genomic sequence and a random text over an alphabet of size 8 or 32.

Download paper: Article in PostScript Article in PDF BibTeX Reference
 PostScript   PDF   BibTeX reference