An efficient algorithm for LCS problem between two arbitrary sequences (Q1720875)

Summary: The longest common subsequence (LCS) problem is a classic computer science problem. For the essential problem of computing LCS between two arbitrary sequences \(s 1\) and \(s 2\), this paper proposes an algorithm taking \(O(n + r)\) space and \(O(r + n^2)\) time, where \(r\) is the total number of elements in the set \(\left\{(i, j) \mid s 1 [i] = s 2 [j]\right\}\). The algorithm can be more efficient than relevant classical algorithms in specific ranges of \(r\).