Longest Common Subsequence

Finds the longest subsequence common to two sequences.

Sequence 1

ABCDE

Sequence 2

ACE

Step 1 of 18

Find the Longest Common Subsequence of "ABCDE" and "ACE". Build a (6)×(4) table bottom-up.

▶Algorithm

LCS(s1, s2):
dp[0][j] = dp[i][0] = 0 for all i, j
for i = 1..n, j = 1..m:
if s1[i−1] == s2[j−1]:
  dp[i][j] = dp[i−1][j−1] + 1
else:
  dp[i][j] = max(dp[i−1][j], dp[i][j−1])
backtrack to reconstruct LCS string

Legend

Current cell

Dependencies

Optimal path

Computed

dp[i][j] = length of LCS of the first i characters of "ABCDE" and the first j characters of "ACE".

1 / 18Speed