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 task
Write lcs(a, b), returning one longest common subsequence of a and b.
Challenge 2
Write int lcs_length(const std::string& a, const std::string& b) using only two rows of the table, the previous one and the current one, so two 5,000-character strings need about 10,000 numbers instead of 25 million.
Challenge 3
Write int longest_palindrome_subseq(const std::string& s): the length of the longest subsequence (not necessarily contiguous) that reads the same forwards and backwards. Use an interval table: L[i][j] for the substring from i to j, filled from short intervals to long ones.