.png){kind=icon}
.png){kind=icon}
Return
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}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
A (k]-tuple common substring (abbr. (k]-CSS) is a sequence of at most k common substrings of two or more strings. A longest (k]-CSS of two strings is known 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 designated number of consecutively matching letters, we propose to find a longest (k]-CSS of two strings whose substrings are of length within [l(1), l(2)]. We present a sliding window based dynamic programming algorithm to find such a longest (k]-CSS of two strings whose lengths are n(1) and n(2) in O(kn(1)n(2)) time and space, the same complexity as without the length bounds l(1) and l(2). 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(kn(1)n(2)) time and O(n(1) + kl(2)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.
Keywords:
Algorithm
Complexity
Common substring
Journal
C
IF:
0
Papers:
24
Citations:
0