Definition
Longest Common Subsequence Problem
Given two strings
and over an alphabet . The longest common subsequence problem asks for the length of a longest string that is a subsequence of both and . Input:
Output: the lengthof the longest string that is a subsequence of both and
Algorithms
Brute-force Algorithm
Definition
Link to originalBrute-force Algorithm (Longest Common Subsequence)
Given two strings
and , the brute-force algorithm for the longest common subsequence problem enumerates every choice of positions in , tests whether the resulting subsequence also occurs in , and returns the greatest accepted length: There are
choices of positions: each position is either retained or omitted. Different choices can produce the same string when letters repeat.
Dynamic Programming Algorithm
Definition
Link to originalDynamic Programming Algorithm (Longest Common Subsequence)
Given two strings
and , the dynamic programming algorithm for the longest common subsequence problem computes the optimum for pairs of prefixes and reuses those results. Use zero-based indices. For a string
, is the letter at index , and is the substring from index to index , including both endpoints. Let
be the length of an LCS of the prefixes and . If one prefix is empty, no non-empty common subsequence is possible:
For non-empty prefixes, compare their last letters:
Return
. Memoisation computes each required state at most once.
Examples
, The longest common subsequences are
of length 3.
The longest common subsequence is
with length .
Both
and are longest common subsequences, each of length .
The longest common subsequence is
with length .
No character appears in both strings. The only common subsequence is the empty string
, so .