Prague Stringology Conference 2020

Igor O. Zavadskyi

Fast Exact Pattern Matching in a Bitstream and 256-ary Strings

A few known techniques of exact pattern matching, such as 2-byte read, fast loop, and sliding search windows, are improved and applied to two related sub-problems. At first, we present a new family of pattern matching algorithms, performing efficiently over 256-ary alphabets. Taking them as an underlying solution, we build the algorithms for searching a string in a bitstream. It turns out that in both cases our algorithms outperform all the other tested methods for all tested pattern lengths.

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