@inproceedings{4164186ae70b437b89024a54444becb3,
title = "Detecting k-(Sub-)Cadences and Equidistant Subsequence Occurrences",
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(n2) time algorithms for finding k-(sub-)cadences and equidistant subsequences. Furthermore, O(n log2 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. 2012 ACM Subject Classification Mathematics of computing ! Combinatorial algorithms.",
keywords = "Bit parallelism, Cadences, Pattern matching, String algorithms, Subsequences",
author = "Mitsuru Funakoshi and Yuto Nakashima and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda and Ayumi Shinohara",
note = "Funding Information: Funding Mitsuru Funakoshi: JSPS KAKENHI Grant Number JP20J21147. Yuto Nakashima: JSPS KAKENHI Grant Number JP18K18002. Shunsuke Inenaga: JSPS KAKENHI Grant Number JP17H01697, JST PRESTO Grant Number JPMJPR1922. Hideo Bannai: JSPS KAKENHI Grant Numbers JP16H02783, JP20H04141. Masayuki Takeda: JSPS KAKENHI Grant Number JP18H04098. Ayumi Shinohara: JSPS KAKENHI Grant Number JP15H05706. Publisher Copyright: {\textcopyright} 2020 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.; 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020 ; Conference date: 17-06-2020 Through 19-06-2020",
year = "2020",
month = jun,
day = "1",
doi = "10.4230/LIPIcs.CPM.2020.12",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Gortz, {Inge Li} and Oren Weimann",
booktitle = "31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020",
address = "Germany",
}