Algorithms for Two Versions of LCS Problem for Indeterminate Strings

摘要

We study the complexity of the longest common subsequence (LCS) problem from a new perspective. By an indeterminate string (i-string, for short) we mean a sequence X = X[1]X[2]... X[n], where I[i] ∈ ∑ for each i, and ∑ is a given alphabet of potentially large size. A subsequence of X is any usual string over ∑ which is an element of the finite (but usually of exponential size) language X[i_1]X[i_2]... X[i_p], where 1 ≤ i_1 < i_2 < i_3... < ip ≤ n,p ≥ 0. Similarly, we define a supersequence of x. Our first version of the LCSrnproblem is Problem ILCS: for given i-strings X and Y, find their longest common subsequence. From the complexity point of view, new parameters of the input correspond to |∑| and maximum size l of the subsets in X and Y. There is also a third parameter R, which gives a measure of similarity between X and Y. The smaller the 1Z, the lesser is the time for solving Problem ILCS. Our second version of the LCS problem is Problem CILCS (constrained ILCS): for given i-strings X and Y and a plain string Z, find the longest common subsequence of X and Y which is, at the same time, a supersequence of Z. In this paper, we present several efficient algorithms to solve both ILCS and CILCS problems. The efficiency in our algorithms are obtained in particular by using an efficient data structure for special type of range maxima queries and fast multiplication of boolean matrices.