Finding Longest Common Subsequence (Dynamic Programming)

Dynamic programming can be effectively applied to solve the Longest Common Subsequence (LCS) problem. The LCS is the longest substring, which belongs to both given strings.

This algorithm differs from the string matching problem. In a string matching problem, a string pattern is searched within another string. However, in LCS a string is not searched with another string. The objective of this algorithm is to determine the maximum matching between two strings.

---

For example, given two sequences, x = "abcbdab" and y = "bdcaba", the LCS(x, y) = { "bcba", "bdab", "bcab" }. Hence, in this example more than one optimal solutions exist.

Firstly, the LCS problem can be solved using a brute-force technique, which is an exponential-time algorithm. The basic concept of this algorithm is to check every subsequence of x[1..m] with all the subsequences of sequence y[1..n].

          = 0                                        if i = 0 or j = 0

c[i,j]  = c[i - 1, j - 1] + 1                 if i, j > 0 and xi = yj

          = max(c[i, j - 1], c[i - 1, j])  if i, j > 0 and xi != yj

The checking takes O(n) time, and there are 2^m subsequences of x. The running time thus is exponential O(n.2m). It is not good for large sequences and the lecture continues with a simplification - let's look at the length of the longest common subsequence and then extend this algorithm to find the LCS itself. The simplified algorithm is recursive in nature and computes the same subproblems.

---

Algorithm to find the Longest Chain Length

---

---

Algorithm to print the Longest Chain

---

---

Example

---

...

Implementation in C Language

#include <stdio.h> #include <string.h> #define MAXN 10000 int max(int a, int b) { return a > b ? a : b; } int LongestCommonSubsequence(char str1[], char str2[]) { int s_len = strlen(str1); int t_len = strlen(str2); int common[s_len + 1][t_len + 1]; int i, j; for (i = s_len; i >= 1; i--) { str1[i] = str1[i - 1]; } for (i = t_len; i >= 1; i--) { str2[i] = str2[i - 1]; } for (i = 0; i <= t_len; i++) { common[0][i] = 0; } for (i = 0; i <= s_len; i++) { common[i][0] = 0; } for (i = 1; i <= s_len; i++) { for (j = 1; j <= t_len; j++) { if (str1[i] == str2[j]) { common[i][j] = common[i - 1][j - 1] + 1; } else { common[i][j] = max(common[i][j - 1], common[i - 1][j]); } } } return common[s_len][t_len]; } int main() { char str1[MAXN], str2[MAXN]; scanf("%s%s", str1, str2); printf("%d\n", LongestCommonSubsequence(str1, str2)); return 0; }

---

Happy Exploring!