Longest common parameterized subsequences with fixed common substring
Anna Gorbenko, Vladimir Popov · Applied Mathematical Sciences · 2013
In this paper we consider the problem of the longest common param-eterized subsequence with fixed common substring (STR-IC-LCPS). In particular, we show that STR-IC-LCPS is NP-complete. We describe an approach to solve STR-IC-LCPS. This approach is based on an explicit reduction from the problem to the satisfiability problem.