On The Longest Common Subsequence Problem- General And Variants

Let X and Y be any two sequences over an alphabet Σ, where each pair of elements in Σ is comparable. The longest common increasing subsequence(LCIS) problem is to find an increasing subsequence S common to both X and Y of greatest length. For any two sequences X and Y over an alphabet Σ, the longest common subsequence problem of X and Y is to find a subsequence S common to both X and Y with greatest length. Unlike the LCIS problem where every pair of input alphabet is comparable, there is no such restriction in the LCS problem. Further the greatest common subsequence found in the LCIS must be strictly increasing, which need not be the case for LCS. Let X, Y and P be any three sequences over an alphabet Σ. The constrained longest common subsequence(CLCS) problem of X and Y with respect to P is to find a longest common subsequence S of X and Y, such that P is a subsequence of S