TY - GEN

T1 - Longest Common Rollercoasters

AU - Fujita, Kosuke

AU - Nakashima, Yuto

AU - Inenaga, Shunsuke

AU - Bannai, Hideo

AU - Takeda, Masayuki

N1 - Funding Information:
Acknowledgments. This work was supported by JSPS KAKENHI Grant Numbers JP18K18002 (YN), JP21K17705 (YN), JP17H01697 (SI), JP20H04141 (HB), JP18H04098 (MT), and JST PRESTO Grant Number JPMJPR1922 (SI).
Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

PY - 2021

Y1 - 2021

N2 - For an integer k≥ 3, a k-rollercoaster is a numeric string such that any maximal strictly non-increasing or non-decreasing substring has length at least k. We consider the problem of computing the longest common k-rollercoaster between two integer strings S and T, i.e., the longest k-rollercoaster that is a subsequence common to both S and T. We give two algorithms that solve this problem; The first runs in O(nmk) time and space, where n, m are respectively the lengths of S and T. The second runs in O(rklog 3mlog log m) time and O(rk) space, where r= O(mn) is the number of pairs (i, j) of matching points such that S[ i] = T[ j], assuming that m≤ n and that S, T only consist of characters which occur in both strings. The second algorithm is faster than the first one when r is sub-linear in nm/log3mloglogm.

AB - For an integer k≥ 3, a k-rollercoaster is a numeric string such that any maximal strictly non-increasing or non-decreasing substring has length at least k. We consider the problem of computing the longest common k-rollercoaster between two integer strings S and T, i.e., the longest k-rollercoaster that is a subsequence common to both S and T. We give two algorithms that solve this problem; The first runs in O(nmk) time and space, where n, m are respectively the lengths of S and T. The second runs in O(rklog 3mlog log m) time and O(rk) space, where r= O(mn) is the number of pairs (i, j) of matching points such that S[ i] = T[ j], assuming that m≤ n and that S, T only consist of characters which occur in both strings. The second algorithm is faster than the first one when r is sub-linear in nm/log3mloglogm.

UR - http://www.scopus.com/inward/record.url?scp=85116761155&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85116761155&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-86692-1_3

DO - 10.1007/978-3-030-86692-1_3

M3 - Conference contribution

AN - SCOPUS:85116761155

SN - 9783030866914

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 21

EP - 32

BT - String Processing and Information Retrieval - 28th International Symposium, SPIRE 2021, Proceedings

A2 - Lecroq, Thierry

A2 - Touzet, Hélène

PB - Springer Science and Business Media Deutschland GmbH

T2 - 28th International Symposium on String Processing and Information Retrieval, SPIRE 2021

Y2 - 4 October 2021 through 6 October 2021

ER -