Name
Abstract | ||
|---|---|---|
Given a positive constant c , a sequence S = (s(1) , s(2) , ... , s(k)) of k numbers is said to be almost increasing if and only if s(i) > max(1 <= j <= i) s(j) - c for all 1 < i <= k. A longest common almost-increasing subsequence (LCaIS) between two input sequences is a longest common subsequence that is also an almost increasing sequence. We found out that the existing algorithm proposed by Moosa et al. [1] to find an LCaIS of two sequences without repeated elements gives an incorrect result for some instances. In this work, we present a dynamic programming algorithm that can correctly compute an LCaIS between any two sequences with repeated elements in O (nml) time and O (nm) space, where n and m are the lengths of two input sequences and l is the length of the output LCaIS. (C) 2020 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1016/j.tcs.2020.11.035 | THEORETICAL COMPUTER SCIENCE |
Keywords | DocType | Volume |
Algorithm, Dynamic programming, Longest common almost-increasing, subsequence | Journal | 854 |
ISSN | Citations | PageRank |
0304-3975 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Toan Thang Ta | 1 | 2 | 1.44 |
| Yi-Kung Shieh | 2 | 1 | 1.04 |
| Chin Lung Lu | 3 | 423 | 34.59 |