Name
Title | ||
|---|---|---|
Parallel Algorithm for Pattern Matching Problems Under Substring Consistent Equivalence Relations. |
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 $\approx$ is called a substring consistent equivalence relation (SCER), if for two strings $X$ and $Y$, $X \approx Y$ implies $|X| = |Y|$ and $X[i:j] \approx Y[i:j]$ for all $1 \le i \le j \le |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(\xi_m^\mathrm{t} \log^2 m)$ time and $O(\xi_m^\mathrm{w} \cdot n \log^2 m)$ work, with $O(\tau_n^\mathrm{t} + \xi_m^\mathrm{t} \log^2 m)$ time and $O(\tau_n^\mathrm{w} + \xi_m^\mathrm{w} \cdot m \log^2 m)$ work preprocessing on the Priority Concurrent Read Concurrent Write Parallel Random-Access Machines (P-CRCW PRAM). |
Year | DOI | Venue |
|---|---|---|
2022 | 10.4230/LIPIcs.CPM.2022.28 | Annual Symposium on Combinatorial Pattern Matching (CPM) |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Davaajav Jargalsaikhan | 1 | 2 | 1.31 |
| Diptarama Hendrian | 2 | 0 | 2.37 |
| Ryo Yoshinaka | 3 | 0 | 2.03 |
| Ayumi Shinohara | 4 | 936 | 88.28 |