A space efficient algorithm for the constrained heaviest common subsequence problem

Let Σ be an alphabet. For each letter in Σ a positive weight is assigned to it. The weight of a string S over Σ is defined as the sum of the weights of the letters in S. For two strings X, Y, and a constrained string P over an alphabet Σ, the constrained heaviest common subsequence problem for two strings X and Y with respect to P is to find a sequence Z such that Z is the heaviest, i.e., having the largest weight, common subsequence for X and Y and P is a subsequence of Z. In this paper an O(|X||Y||Z|) time and O((|X|+|Y|)|P|) space algorithm for the constrained heaviest common subsequence problem of two strings is presented, where |X|, |Y|, and |P| denote the lengths of string X, Y, P, respectively.