longest common subsequence
The longest sequence of characters that appears, in order but not necessarily side by side, in both of two strings.
In more detail
Dynamic programming fills a table over all prefix pairs in O(m × n) and a traceback recovers the subsequence itself. Diff tools use LCS to find the lines two files share.
Example
ABCBDAB and BDCAB share the subsequence BCAB, of length four.Related terms
- subsequence — The characters or items left after deleting some, or none, from a sequence without changing the order of the rest.
- dynamic programming — A technique that solves a problem by breaking it into overlapping subproblems, solving each only once and storing the answers for reuse.
- traceback — Walking back through a filled dynamic-programming table from the final cell to recover the choices that produced the optimal answer.
- edit distance — The minimum number of single-character insertions, deletions and substitutions needed to turn one string into another.
Taught in
- Dynamic Programming: Memoisation And Tabulation — Algorithms & Data Structures for Working Engineers