Guohui Lin

Polynomial-time equivalences and refined algorithms for longest common subsequence variants

2024 · Discrete Applied Mathematics

The problem of computing the longest common subsequence of two sequences ( LCS for short) is a classical and fundamental problem in computer science. In this article, we study four variants of LCS : the …