The problem of finding the constrained longest common subsequence (CLCS) for thesequences A and B with respect to the sequence P was introduced recently. Its goal is to find the longestsubsequence of A and B such that P is a subsequence of it. The best known algorithms for its solvingrequire time of order of a product of the sequence lengths. We introduce a novel approach in which timeand space complexities depend also on the number of matches between A, B, and P. The time complexityis better for typical parameter settings and never worse.