.png){kind=icon}
返回
Longest Double-Bounded (k]-Tuple Common Substrings
.png){kind=icon}
PRE
AI
DOI：10.1007/978-981-95-0218-9_26.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
(k]-元组公共子串（缩写为(k]-CSS）是两个或多个字符串中最多k个公共子串的序列。两个字符串的最长(k]-CSS已知可在二次时间、线性空间内检索，甚至当k为常数时，可在次二次时间和空间内完成。受需要指定连续匹配字母数量的(k]-CSS的计算生物学应用的启发，我们提出寻找两个字符串的最长(k]-CSS，其子串长度在[l(1), l(2)]范围内。我们提出一种基于滑动窗口的动态规划算法，用于在O(kn(1)n(2))时间和空间内找到长度分别为n(1)和n(2)的两个字符串的最长(k]-CSS，其复杂度与无长度限制l(1)和l(2)时相同。通过基于滚动数组的动态规划预先获取最长(k]-CSS的长度，我们提出一种分治算法，用于在O(kn(1)n(2))时间和O(n(1) + kl(2)n(2))空间内找到这样的最长(k]-CSS，该算法旨在处理更长的给定字符串。我们还提出一种算法，用于在O(n log(2) n)时间内找到这样的最长(2]-CSS，其中n是输入字符串的总长度。
Keyword:
Algorithm
Complexity
Common substring
期刊
C
IF:
0
论文数:
24
被引数:
0
机构
引用论文
分享收藏分享收藏Comparative genomics identifies thousands of candidate structured RNAs in human microbiomes.png)
GENOME BIOLOGY
OAAI
GENOME BIOLOGYIF9.4
OAAI分享收藏
查看更多内容