An efficient algorithm for LCS problem between two arbitrary sequences (Q1720875)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An efficient algorithm for LCS problem between two arbitrary sequences |
scientific article |
Statements
An efficient algorithm for LCS problem between two arbitrary sequences (English)
0 references
8 February 2019
0 references
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\).
0 references
0 references