Slides for our paper "On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching" presented at CPM 2016
Abstract
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).