Scholarlink

A ( \(k\) ]-tuple common substring (abbr. ( \(k\) ]-CSS) is a common subsequence of multiple given strings including at most \(k\) common substrings. This pattern of two strings is retrievable in quadratic time and linear space and even more, in subquadratic time and space if \(k\) is a constant. Motivated by computational biology applications in need of a ( \(k\) ]-CSS with substantially many consecutive matches, we propose to find a longest ( \(k\) ]-CSS of two strings whose substrings are of length at least \(l\) , of which the complexity is indefinite. We present a dynamic programming algorithm to find such a longest ( \(k\) ]-CSS of two strings whose lengths are \({n}_{1}\) and \({n}_{2}\) in \(O(k{n}_{1}{n}_{2})\) time and space, the same complexity as without the length bound \(l\) . Through rolling array based dynamic programming to get the longest ( \(k\) ]-CSS length in advance, we present a divide-and-conquer algorithm to find such a longest ( \(k\) ]-CSS in \(O(k{n}_{1}{n}_{2})\) time and \(O({n}_{1}+kl{n}_{2})\) space, which is intended to work for two much longer given strings. We also present an algorithm to find such a longest ( \(2\) ]-CSS in \(O(n{log}^{2}n)\) time where \(n\) is the total length of input strings.

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

Enough Consecutive Matches in k-Tuple Common Substrings

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Tiantian Li,
  • Siqi Jiang,
  • Haitao Jiang,
  • Lianrong Pu,
  • Haodi Feng,
  • Xuefeng Cui,
  • Lizhen Cui,
  • Daming Zhu

摘要

A ( \(k\) ]-tuple common substring (abbr. ( \(k\) ]-CSS) is a common subsequence of multiple given strings including at most \(k\) common substrings. This pattern of two strings is retrievable in quadratic time and linear space and even more, in subquadratic time and space if \(k\) is a constant. Motivated by computational biology applications in need of a ( \(k\) ]-CSS with substantially many consecutive matches, we propose to find a longest ( \(k\) ]-CSS of two strings whose substrings are of length at least \(l\) , of which the complexity is indefinite. We present a dynamic programming algorithm to find such a longest ( \(k\) ]-CSS of two strings whose lengths are \({n}_{1}\) and \({n}_{2}\) in \(O(k{n}_{1}{n}_{2})\) time and space, the same complexity as without the length bound \(l\) . Through rolling array based dynamic programming to get the longest ( \(k\) ]-CSS length in advance, we present a divide-and-conquer algorithm to find such a longest ( \(k\) ]-CSS in \(O(k{n}_{1}{n}_{2})\) time and \(O({n}_{1}+kl{n}_{2})\) space, which is intended to work for two much longer given strings. We also present an algorithm to find such a longest ( \(2\) ]-CSS in \(O(n{log}^{2}n)\) time where \(n\) is the total length of input strings.