Slides presented at 2016 Workshop über Algorithmen und Komplexität (Theorietag): "On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching"
We present parallel algorithms for exact and approximate pattern matching with suffix arrays, using a CREW-PRAM with processors. Given a static text of length , we first show how to compute the suffix array interval of a given pattern of length in time for . For approximate pattern matching with differences or mismatches, we show how to compute all occurrences of a given pattern in time, where is the size of the alphabet and . The workhorse of our algorithms is a data structure for merging suffix array intervals quickly: Given the suffix array intervals for two patterns and , we present a data structure for computing the interval of in sequential time, or in parallel time. All our data structures are of size bits (in addition to the suffix array).