The Prague Stringology Conference 2006

Jan Šupol and Bořivoj Melichar

2D Bitwise Memory Matrix: A Tool for Optimal Parallel Approximate Pattern Matching

A very fast parallel approach to pattern matching is presented. The approach is based on the bit-parallel approach and we use two-dimensional bitwise memory matrix which helps to achieve very fast parallel pattern matching algorithms. The parallel pattern matching takes O(1) time for the exact pattern matching and O(k) for the approximate pattern matching, where k is the number of errors.

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