Scholarlink

A (k]-tuple common substring (abbr. (k]-CSS) is a common subsequence of two or more given strings including at most k common substrings. The complexity of finding a longest (k]-CSS of 2 strings is still open. We present a dynamic programming algorithm for finding a longest (k]-CSS of two strings in \(O(kn_1n_2)\) time and space where \(n_1\) and \(n_2\) are the given string lengths. To breakthrough the quadratic space complexity, we present an algorithm for finding a longest (k]-CSS in \(O(kn_1n_2)\) time and \(O(n_1+kn_2)\) space.

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

Longest (k]-Tuple Common Substrings

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Tiantian Li,
  • Haitao Jiang,
  • Lusheng Wang,
  • Daming Zhu

摘要

A (k]-tuple common substring (abbr. (k]-CSS) is a common subsequence of two or more given strings including at most k common substrings. The complexity of finding a longest (k]-CSS of 2 strings is still open. We present a dynamic programming algorithm for finding a longest (k]-CSS of two strings in \(O(kn_1n_2)\) time and space where \(n_1\) and \(n_2\) are the given string lengths. To breakthrough the quadratic space complexity, we present an algorithm for finding a longest (k]-CSS in \(O(kn_1n_2)\) time and \(O(n_1+kn_2)\) space.