conference

Longest Common Subsequence in at Least k Length Order-Isomorphic Substrings

Yohei Ueki, Diptarama, Masatoshi Kurihara, Yoshiaki Matsuoka, Kazuyuki Narisawa, Ryo Yoshinaka, Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara

Theory and Practice of Computer Science - 43rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2017), Lecture Notes in Computer Science Vol.10139, pp.363-374 (2017), [peer-reviewed]
Event Date: January 16-20, 2017

開催地: Limerick, Ireland

SOFSEM

DOI: 10.1007/978-3-319-51963-0_28 External Link

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.