Longest Double-Bounded (k]-Tuple Common Substrings
摘要
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_1n_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_1n_2)\) time and \(O(n_1+kl_2n_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 ^2n)\) time where n is the total length of input strings.