Longest Common Subsequence in at Least k Length Order-Isomorphic Substrings
| Autor: | Kazuyuki Narisawa, Yohei Ueki, Ayumi Shinohara, Shunsuke Inenaga, Yoshiaki Matsuoka, Hideo Bannai, Diptarama, Masatoshi Kurihara, Ryo Yoshinaka |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Order isomorphism
0102 computer and information sciences 02 engineering and technology Longest increasing subsequence 01 natural sciences Substring Running time Longest common subsequence problem Combinatorics Dynamic programming 010201 computation theory & mathematics Subsequence 0202 electrical engineering electronic engineering information engineering Order (group theory) 020201 artificial intelligence & image processing Mathematics |
| Zdroj: | SOFSEM 2017: Theory and Practice of Computer Science ISBN: 9783319519623 SOFSEM |
| DOI: | 10.1007/978-3-319-51963-0_28 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|