Scholarlink

The Longest Common Subsequence (LCS) problem is a classical problem in computer science. Numerous variants of the LCS problem have been proposed due to its significance. In this paper, we study a new variant of the LCS problem that combines two settings: the input strings are compressed using run-length encoding (RLE) and the solution must consist of matching substrings of length k, as in the LCSk problem. We propose two algorithms to address the challenges of the k-length substring constraint. The first requires \(O(nM + mN)\)  time where n and m are the lengths of the uncompressed input strings, N and M are the lengths of the compressed input strings. The second requires \(O(N+M+ \min \{n+|C| \log \log m,\ m+ |C| \log \log n\})\) time, where |C| denotes the number of required k-length matching substrings between the input strings.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Longest Common Subsequence in K-Length Substrings for Run-Length Encoded Strings

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • B. Riva Shalom,
  • Eitan Kondratovsky,
  • Ely Porat

摘要

The Longest Common Subsequence (LCS) problem is a classical problem in computer science. Numerous variants of the LCS problem have been proposed due to its significance. In this paper, we study a new variant of the LCS problem that combines two settings: the input strings are compressed using run-length encoding (RLE) and the solution must consist of matching substrings of length k, as in the LCSk problem. We propose two algorithms to address the challenges of the k-length substring constraint. The first requires \(O(nM + mN)\)  time where n and m are the lengths of the uncompressed input strings, N and M are the lengths of the compressed input strings. The second requires \(O(N+M+ \min \{n+|C| \log \log m,\ m+ |C| \log \log n\})\) time, where |C| denotes the number of required k-length matching substrings between the input strings.