Step 4 of 6
Longest common subsequence
A subsequence keeps some characters of a string, in order, but not necessarily next to each other: ace is a subsequence of abcde. The longest common subsequence (LCS) of two strings is the longest string that's a subsequence of both. It's what diff and git use to line up two versions of a file (with lines instead of characters): everything in the LCS is unchanged, and the rest was added or deleted. Biologists use the same idea to compare DNA.
The table
Let L[i][j] be the LCS length of the first i characters of a and the first j characters of b. Look at the last character of each prefix, a[i - 1] and b[j - 1]:
- If they're equal, that character can end the common subsequence:
L[i][j] = L[i - 1][j - 1] + 1. - If they differ, at least one of them isn't used, so drop one or the other and keep the better result:
L[i][j] = max(L[i - 1][j], L[i][j - 1]).
Row 0 and column 0 (an empty prefix) are all 0.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
int main() {
std::string a = "ABCBDAB", b = "BDCABA";
std::size_t n = a.size(), m = b.size();
std::vector<std::vector<int>> L(n + 1, std::vector<int>(m + 1, 0));
for (std::size_t i = 1; i <= n; i++)
for (std::size_t j = 1; j <= m; j++)
L[i][j] = (a[i - 1] == b[j - 1]) ? L[i - 1][j - 1] + 1
: std::max(L[i - 1][j], L[i][j - 1]);
std::cout << " ";
for (char c : b) std::cout << c << " ";
std::cout << "\n";
for (std::size_t i = 1; i <= n; i++) {
std::cout << a[i - 1] << " | ";
for (std::size_t j = 1; j <= m; j++) std::cout << L[i][j] << " ";
std::cout << "\n";
}
std::cout << "LCS length: " << L[n][m] << "\n";
}
B D C A B A
A | 0 0 0 1 1 1
B | 1 1 1 1 2 2
C | 1 1 2 2 2 2
B | 1 1 2 2 3 3
D | 1 2 2 2 3 3
A | 1 2 2 3 3 4
B | 1 2 2 3 4 4
LCS length: 4
The table has (n + 1) × (m + 1) entries, each filled in O(1), so LCS takes O(n × m) time. Trying every subsequence of a instead would take 2ⁿ.
Getting the string back
The table stores lengths, but it also records which choice produced each entry, so the subsequence itself can be recovered by walking backward from L[n][m]:
- If
a[i - 1] == b[j - 1], that character is part of the LCS. Add it, and move diagonally to(i - 1, j - 1). - Otherwise, move to whichever of
(i - 1, j)and(i, j - 1)has the larger value (either one on a tie). - Stop when
iorjreaches 0.
The characters come out last first, so reverse the string at the end. Often several different strings share the maximum length (BCBA and BDAB both work above); any one of them is a correct answer.
Your turn: write lcs(a, b), returning one longest common subsequence of a and b.