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

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

DOI 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…

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