On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching

Johannes Fischer, Dominik Köppl & Florian Kurpicz
We present parallel algorithms for exact and approximate pattern matching with suffix arrays, using a CREW-PRAM with p processors. Given a static text of length n, we first show how to compute the suffix array interval of a given pattern of length m in O(m/p + lg p + lg lg p * lg lg n) time for p <= m. For approximate pattern matching with k differences or mismatches, we show how to compute...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.