Fast Algorithm for Constrained Longest Common Subsequence Problem

The problem of finding the constrained longest common subsequence (CLCS) for the sequences A and B with respect to the sequence P was introduced recently. The best known algorithms for its solving requires time of order of a product of the sequences length. We introduce a novel approach in which time and memory complexities depends on the number of matches between A, B, and P. The time complexity is never worse than the one of the known algorithms, but typically is better. Experiments show that our method is faster than the known ones and requires less memory. 1 Introduction an