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.