Doubly-Constrained LCS and Hybrid-Constrained LCS problems revisited

We revisit two recently studied variants of the classic Longest Common Subsequence (LCS) problem, namely, the Doubly-Constrained LCS (DC-LCS) and Hybrid-Constrained LCS (HC-LCS) problems. We present finite automata based algorithms for both problems.

► We revisit two recently studied variants of the classic Longest Common Subsequence (LCS) problem. ► In particular we study the Doubly-Constrained LCS (DC-LCS) and Hybrid-Constrained LCS (HC-LCS) problems. ► We present finite automata based algorithms for both the problems. ► For DC-LCS, we devise an exact algorithm and a fixed-parameter algorithm where the parameter is the length of the solution. ► For the HC-LCS problem, we can also handle arbitrary number of constraint patterns.