2026-10-09T14:56:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12137 2024-03-06T09:49:23Z ddc:004 open_access

Detecting k-(Sub-)Cadences and Equidistant Subsequence Occurrences Funakoshi, Mitsuru Nakashima, Yuto Inenaga, Shunsuke Bannai, Hideo Takeda, Masayuki Shinohara, Ayumi string algorithms pattern matching bit parallelism subsequences cadences 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²) time algorithms for finding k-(sub-)cadences and equidistant subsequences. Furthermore, O(nlog² n) and O(nlog 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mitsuru Funakoshi and Yuto Nakashima and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda and Ayumi Shinohara 2020 Is Part Of LIPIcs, Volume 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2020.12 urn:nbn:de:0030-drops-121375 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2020.12 eng https://creativecommons.org/licenses/by/3.0/legalcode