Name
Abstract | ||
|---|---|---|
We consider the longest common subsequence (LCS) problem with the restriction that the common subsequence is required to consist of at least k length substrings. First, we show an O(mn) time algorithm for the problem which gives a better worst-case running time than existing algorithms, where m and n are lengths of the input strings. Furthermore, we mainly consider the LCS in at least k length order isomorphic substrings problem. We show that the problem can also be solved in O(mn) worst-case time by an easy-to-implement algorithm. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/978-3-319-51963-0_28 | Lecture Notes in Computer Science |
Keywords | DocType | Volume |
Longest common subsequence,Dynamic programming,Order-isomorphism,Order-preserving matching | Conference | 10139 |
ISSN | Citations | PageRank |
0302-9743 | 2 | 0.40 |
References | Authors | |
8 | 9 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yohei Ueki | 1 | 2 | 0.40 |
| Diptarama | 2 | 4 | 1.85 |
| Masatoshi Kurihara | 3 | 2 | 0.40 |
| Yoshiaki Matsuoka | 4 | 2 | 1.07 |
| Kazuyuki Narisawa | 5 | 33 | 6.82 |
| Ryo Yoshinaka | 6 | 172 | 26.19 |
| Hideo Bannai | 7 | 620 | 79.87 |
| Shunsuke Inenaga | 8 | 595 | 79.02 |
| Ayumi Shinohara | 9 | 936 | 88.28 |