Detecting $k$-(Sub-)Cadences and Equidistant Subsequence Occurrences.
The 31st Annual Symposium on Combinatorial Pattern Matching (CPM2020),
LIPIcs Vol.161, pp.12:1-12:11
(2020), [peer-reviewed]
Event Date:
June 17-19, 2020
@ online
Abstract / 概要
The equidistant subsequence pattern matching problem is considered. Given a pattern string $P$ and a text string $T$, we say that $P$ is an 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.