In this paper, we present a finite automata based algorithm for solving the constrained
longest
common
subsequence problem for degenerate
strings. A string is a sequence of symbols from a given alphabet Σ. A subsequence
u of a string x is obtained by deleting some characters from u (not necessarily contiguous). Given two strings x and y, u is a common
subsequence of x and y, if u is a subsequence of both x and y. And, u is a longest
common
subsequence (LCS) of x and y, if it is the longest among all such subsequences. Given two strings x and y, the LCS problem aims to compute a longest common subsequence of them. We study a newer variant of the classic LCS problem,
namely the Constrained LCS problem (CLCS). In CLCS, the computed longest common subsequence must also be a supersequence of
a third given string, say z [3,2,1].
Partially supported by the Ministry of Education under research program MSM 6840770014 and the Czech Science Foundation as
project No. 201/06/1039.