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

oai:drops-oai.dagstuhl.de:16155 2024-03-06T10:56:42Z ddc:004 open_access

Parallel Algorithm for Pattern Matching Problems Under Substring Consistent Equivalence Relations Jargalsaikhan, Davaajav Hendrian, Diptarama Yoshinaka, Ryo Shinohara, Ayumi parallel algorithm substring consistent equivalence relation pattern matching Given a text and a pattern over an alphabet, the pattern matching problem searches for all occurrences of the pattern in the text. An equivalence relation ≈ is a substring consistent equivalence relation (SCER), if for two strings X and Y, X ≈ Y implies |X| = |Y| and X[i:j] ≈ Y[i:j] for all 1 ≤ i ≤ j ≤ |X|. In this paper, we propose an efficient parallel algorithm for pattern matching under any SCER using the "duel-and-sweep" paradigm. For a pattern of length m and a text of length n, our algorithm runs in O(ξ_m^t log³ m) time and O(ξ_m^w ⋅ n log² m) work, with O(τ_n^t + ξ_m^t log² m) time and O(τ_n^w + ξ_m^w ⋅ m log² m) work preprocessing on the Priority Concurrent Read Concurrent Write Parallel Random-Access Machines (P-CRCW PRAM), where τ_n^t, τ_n^w, ξ_m^t, and ξ_m^w are parameters dependent on SCERs, which are often linear in n and m, respectively. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Davaajav Jargalsaikhan and Diptarama Hendrian and Ryo Yoshinaka and Ayumi Shinohara 2022 Is Part Of LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2022.28 urn:nbn:de:0030-drops-161552 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.28 eng https://creativecommons.org/licenses/by/4.0/legalcode