Longest Common Subsequence
Tags: Algorithm, dynamic programmingA subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. It is a set of characters that appear in left-to-right order, but not necessarily consecutively.
Longest common subsequence (LCS) of 2 sequences is a subsequence, with maximal length, which is common to both the sequences.
Problem definition of Longest Common Subsequence
- Given the first sequence which contains (m) symbols X = (x1, x2, x3, …, xm)
- Given the second sequence which contains (n) symbols Y = (y1, y2, y3, …, yn)
- Find the longest common sequence (Z) between (X) and (Y) call it Z = (z1, z2, z3, …, zk)
See the following example:
The longest common subsequence of the two strings are AAAATTCA
Analysis
Let the input sequences be X[0..m-1] and Y[0..n-1] of lengths m and n respectively. And let L(X[0..m-1], Y[0..n-1]) be the length of LCS of the two sequences X and Y. We can recursive define L(X[0..m-1], Y[0..n-1]) as following:
- If the last characters of both sequences match (e.g.
X[m-1] == Y[n-1]) then
L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2])
- If the last characters of both sequences do not match (or
X[m-1] != Y[n-1]) then
L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2])
We can easily implement the recursive algorithm based on the above idea:
|
1 2 3 4 5 6 7 |
def lcs(X, Y, m, n): if m == 0 or n == 0: return 0; elif X[m-1] == Y[n-1]: return 1 + lcs(X, Y, m-1, n-1); else: return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n)); |
The above naive recursive algorithm has time complexity of O(2^n) in worst case when all characters of X and Y do not match. The reason for this high complexity is because there are many subproblems solved again and again. One way to improve is to use Memorization, which records the answers of the subproblems for reuse in the following calls thus avoiding repeated calculation.
Another method is to use dynamic programming, which uses a table to solve the problem in a bottom up manner.
We define a table C, where C[i, j] denotes the LCS (Longest Common Subsequence) of X[0 .. i - 1] and Y[0..j - 1].
Then we have the following rule to update the table for i from 1 to m and j from 1 to n given the input X[0 .. m-1] and Y[0 .. n - 1].
C[i, j] = 0 if i = 0 or j = 0 // this means X[0..i - 1]] is empty or Y[0..j - 1] is empty, C[i, j] = 0
C[i, j] = 1 + C[i-1, j-1] if i > 0 and j > 0 and X[i - 1] == Y[j - 1]
C[i, j] = max (C[i, j-1], C[i-1, j]) if i > 0 and j > 0 and X[i - 1] != Y[j - 1]
See the following code that is accepted by hackerrank:
|
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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
import java.io.*; import java.util.*; public class Solution { static void read(int[] str, int size, Scanner s){ for(int i = 0; i < size; i++) { str[i] = s.nextInt(); } } public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner s = new Scanner(System.in); String[] lines = s.nextLine().split(" "); int n = Integer.valueOf(lines[0]); int m = Integer.valueOf(lines[1]); int[] X = new int[n]; int[] Y = new int[m]; read(X, n, s); read(Y, m, s); int[][] C = lcs(X, Y); StringBuilder res = new StringBuilder(); getLcs(C, X, X.length, Y, Y.length, res); System.out.println(res.toString().trim()); //System.out.println(X[0]); } static int[][] lcs(int[] X, int[] Y) { int m = X.length; int n = Y.length; int[][] C = new int[m + 1][n + 1]; // int[] b = new int[]; //j = 0 means Y[0 .. j -1] is empty, thus C[i, j] = 0 for (int i = 1; i <= m; i++) { C[i][0] = 0; } //i = 0 means X[0 .. i - 1] is empty, thus C[i, j] = 0 for (int j = 1; j <= n; j++) { C[0][j] = 0; } int xi; int yj; //X has m letters for (int i = 1; i <= m; i++) { //Y has n letters for (int j = 1; j <= n; j++) { xi = X[i - 1]; yj = Y[j - 1]; if (xi == yj) { C[i][j] = 1 + C[i - 1][j - 1]; } else if (C[i - 1][j] >= C[i][j - 1]) { C[i][j] = C[i - 1][j]; } else { C[i][j] = C[i][j - 1]; } } } return C; } static void getLcs(int[][] C, int[] X, int xi, int[] Y, int yi, StringBuilder res) { if(xi <= 0 || yi <= 0) { res.append(""); return; } if(X[xi - 1] == Y[yi - 1]) { getLcs(C, X, xi - 1, Y, yi - 1, res); res.append(X[xi - 1] + " "); } else if (C[xi - 1][yi] > C[xi][yi - 1]) { getLcs(C, X, xi - 1, Y, yi, res); } else { getLcs(C, X, xi, Y, yi - 1, res); } } } //input 5 6 1 2 3 4 1 3 4 1 2 1 3 //output 3 4 1 |
You can submit and test your code at hackerrank using the following link:
https://www.hackerrank.com/challenges/dynamic-programming-classics-the-longest-common-subsequence
Here are some good resources to learn longest common subsequence problem:
http://www.8bitavenue.com/2011/11/dynamic-programming-longest-common-subsequence/
http://www.columbia.edu/~cs2035/courses/csor4231.F11/lcs.pdf
http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/
https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
