Parallel algorithm for pattern matching problems under substring consistent equivalence relations

2022/02/27 by Jargalsaikhan, Davaajav, Hendrian, Diptarama, Yoshinaka, Ryo +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2202.13284

Abstract

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 called 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).

Related

• Generalized Dictionary Matching under Substring Consistent Equivalence\n Relations
• Duel and sweep algorithm for order-preserving pattern matching
• Fast Pattern Matching in Strings
• Parallel Algorithm for Longest Common Subsequence in a String
• On the Benefit of Merging Suffix Array Intervals for Parallel Pattern\n Matching