# Algorithms – Dynamic Programming – Longest Common Subsequence (LCS)

Let’s implement the following problem:

Given two strings A and B of equal lengths, containing only lower case letters, our job is to count the minimum number of changes required on string A to make it equal to string B.

Let’s first talk what is a subsequence. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.

For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”.

LCS for “**A**BC**D**G**H**” and “**A**E**D**F**H**R” => length 3

LCS for “AG**GTAB**” and “**G**X**T**X**A**Y**B**” => length 4

The algorithm is quite simple.

Given two array of characters X and Y, of length m and n respectively:

- IF last characters of both sequences match (X[m-1] == Y[n-1]):
- LCS(X[0, m-1], Y[0, n-1] = 1 + LCS(X[0, m-2], Y[0, n-2]

- Else:
- LCS(X[0, m-1], Y[0, n-1] = MAX( LCS(X[0, m-2], Y[0, n-1]), LCS(X[m-1], Y[0, n-2]) )

Still not clear? See the following code.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#include <iostream> #include <iomanip> #include <algorithm> #include <string> using namespace std; int LCS(const string& X, const string& Y, const int m, const int n) { if (m == 0 || n == 0) return 0; if (X[m - 1] == Y[n - 1]) return 1 + LCS(X, Y, m - 1, n - 1); return std::max(LCS(X, Y, m - 1, n), LCS(X, Y, m, n - 1)); } int main() { std::cout << "Usecase" << std::setw(10) << "Result" << std::endl; std::cout << "{abc, ABC}" << std::setw(10) << LCS("abc", "abc", 3, 3); std::cout << "{abc, ABd}" << std::setw(10) << LCS("abc", "abd", 3, 3); std::cin.get(); return 0; } |

The problem with this is the following: We calculate the same code multiple times:

Let’s check the code which uses the dynamic programming approach.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <iostream> #include <iomanip> #include <algorithm> #include <string> #include <vector> using namespace std; int LCS(const string& X, const string& Y) { vector<vector<int>> data(X.size() + 1, vector<int>(Y.size() + 1)); for (uint32_t i = 0; i <= X.size(); ++i) { for (uint32_t j = 0; j <= Y.size(); ++j) { if (i == 0 || j == 0) data[i][j] = 0; else if (X[i - 1] == Y[i - 1]) data[i][j] = 1 + data[i - 1][j - 1]; else data[i][j] = std::max(data[i - 1][j], data[i][j - 1]); } } return data[X.size()][Y.size()]; } int main() { cout << "Usecase" << "Result"; cout << "{abc, abc}" << LCS("abc", "abc"); cout << "{abc, ABd}" << LCS("abc", "ABd"); cout << "{aieou, axixexoxu}" << LCS("aieou", "axixexoxu"); cout << "{AGGTAB, GXTXAYB}" << LCS("AGGTAB", "GXTXAYB"); std::cin.get(); return 0; } |

And this is an example of how it works.