论文标题
在基因一致的等效关系下用于模式匹配问题的平行算法
Parallel algorithm for pattern matching problems under substring consistent equivalence relations
论文作者
论文摘要
给定字母上的文本和模式，模式匹配的问题搜索文本中的所有情况。等价关系$ \ of $ $称为子字符串一致的等价关系（SCER），如果对于两个字符串$ x $和$ y $，$ x \ y $，y $表示$ | x | = | y | $和$ x [i：j] \大约y [i：j] $ for ahl $ 1 \ le i \ le J \ le | x | $。在本文中，我们提出了一种使用“ Duel-Sweep”范式在任何SCER下进行模式匹配的有效平行算法。对于长度$ m $和长度$ n $的图案，我们的算法以$ o（ξ_m^\ mathrm {t} \ log^2 m）$ time和$ o（ξ_m^\ mathrm {w} \ cdot n \ log^2 m）$（$ o）工作，$ o o（$ o） ξ_m^\mathrm{t} \log^2 m)$ time and $O(τ_n^\mathrm{w} + ξ_m^\mathrm{w} \cdot m \log^2 m)$ work preprocessing on the Priority Concurrent Read Concurrent Write Parallel Random-Access Machines (P-CRCW PRAM).
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(ξ_m^\mathrm{t} \log^2 m)$ time and $O(ξ_m^\mathrm{w} \cdot n \log^2 m)$ work, with $O(τ_n^\mathrm{t} + ξ_m^\mathrm{t} \log^2 m)$ time and $O(τ_n^\mathrm{w} + ξ_m^\mathrm{w} \cdot m \log^2 m)$ work preprocessing on the Priority Concurrent Read Concurrent Write Parallel Random-Access Machines (P-CRCW PRAM).
