论文标题
检测$ k $ - （子）节奏和等距的子序列发生
Detecting $k$-(Sub-)Cadences and Equidistant Subsequence Occurrences
论文作者
论文摘要
考虑了等距的子序列模式匹配问题。给定图案字符串$ p $和文本字符串$ t $，我们说$ p $是$ t $的\ emph {等级的子序列}，如果$ p $是文本的子序列，以至于出现在发生的连续符号$ p $。我们可以将等距子序列的问题视为（子）节奏的概括。我们提供的位平行算法可产生$ o（n^2）$ time算法，以查找$ k $ - （子）节奏和等距子序列。此外，$ o（n \ log^2 n）$和$ o（n \ log n）$ time算法，分别适用于均衡和abelian等均衡器匹配的情况。 = 3 $，显示。该算法利用了最近引入的技术，该技术可以有效地计算有线性约束的卷积。
The equidistant subsequence pattern matching problem is considered. Given a pattern string $P$ and a text string $T$, we say that $P$ is an \emph{equidistant subsequence} of $T$ if $P$ is a subsequence of the text such that consecutive symbols of $P$ in the occurrence are equally spaced. We can consider the problem of equidistant subsequences as generalizations of (sub-)cadences. We give bit-parallel algorithms that yield $o(n^2)$ time algorithms for finding $k$-(sub-)cadences and equidistant subsequences. Furthermore, $O(n\log^2 n)$ and $O(n\log n)$ time algorithms, respectively for equidistant and Abelian equidistant matching for the case $|P| = 3$, are shown. The algorithms make use of a technique that was recently introduced which can efficiently compute convolutions with linear constraints.
