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 -