The substring inclusion constraint longest common subsequence problem can be solved in quadratic time ?
In this paper, we study some variants of the Constrained Longest Common Subsequence (CLCS) problem, namely, the substring inclusion CLCS (Substring-IC-CLCS) problem and a generalized version thereof. In the Substring-IC-CLCS problem, we are to find a longest common subsequence (LCS) of two given strings containing a third constraint string (given) as a substring. Previous solution to this problem runs in cubic time, i.e, O(nmk) O ( n m k ) time, where n,m n , m and k  are the length of the 3 input strings. In this paper, we present simple O(nm) O ( n m ) time algorithms to solve the Substring-IC-CLCS problem. We also study the Generalized Substring-IC-LCS problem where we are given two strings of length n and m respectively and an ordered list of p  strings and the goal is to find an LCS containing each of them as a substring in the order they appear in the list. We present an O(nmp) O ( n m p ) algorithm for this generalized version of the problem.
longest common subsequence algorithms dynamic programming