2026-07-22T06:50:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6066 2024-03-06T10:37:36Z ddc:004 open_access

On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching Fischer, Johannes Köppl, Dominik Kurpicz, Florian parallel algorithms pattern matching approximate string matching 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 all occurrences of a given pattern in O((m^k sigma^k)/p max (k, lg lg n) + (1+m/p) lg p * lg lg n + occ} time, where sigma is the size of the alphabet and p <= sigma^k m^k. The workhorse of our algorithms is a data structure for merging suffix array intervals quickly: Given the suffix array intervals for two patterns P and P', we present a data structure for computing the interval of PP' in O(lg lg n) sequential time, or in O(1 + lg_p lg n) parallel time. All our data structures are of size O(n) bits (in addition to the suffix array). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Johannes Fischer and Dominik Köppl and Florian Kurpicz 2016 Is Part Of LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2016.26 urn:nbn:de:0030-drops-60669 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.26 eng https://creativecommons.org/licenses/by/3.0/legalcode