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

Taught in

References