Algorithm

Longest Common Subsequence of Arrays

Given two arrays: array A of length m [A(1..m)], and array B of length n [B(1..n)], find the longest common subsequence.
The longest sequence of elements that appear left-to-right (but not necessarily in a contiguous block) in both the arrays.
For example:
if a = [1 2 3 4 1] and b =[3 4 1 2 1 3], the LCS(a, b) = [1 2 3]

If there are two arrays (as above) and if lines are drawn from the digits in the first array to the corresponding digit in the second, so that no two lines cross, then it can be represented as:

         1  2     3  4  1 
         |  |     |
   3  4  1  2  1  3

It can be seen that the current digits of A & B may or may not match. In that case, it is not possible for both of them to be part of a common subsequence. Once it is decided what to do with the first digit of the arrays, the remaining sub problem is again a LCS problem, on two shorter arrays. Therefore it can be solved recursively.

The solution to LCS should find two sequences in A and B  with the following 

  • Starting index of sequence in A is i and the starting index of sequence in B is j
  • A[i …m] is a subarray of A starting at index i and going until the end of A, and that B[j …n] is a subarray of B starting at index j and going until the end of B.

Based on the above assumptions, these are the possibilities

  1. If A[i] == B[j] : 1 + LCS(i + 1,j + 1)
  2. If A[i] ≠ B[j]. LCS(i,j + 1) // skipping jth digit of B
  3. If A[i] ≠ B[j]. LCS(i + 1,j) // skipping ith digit of A

If A[i] is equal to B[j], then total length of the LCS can be incremented by 1. Otherwise, LCS will searched by skipping either ith digit of A or jth digit of B.

Now, LCS(i,j) can be revised as:

LCS(i,j) =0 {if i==m or j==n}
LCS(i,j) =1 + LCS(i+1, j+1) {if m ==0 or n==0}
LCS(i,j) = MAX(LCS(i,j+1) + LCS(i+1,j))
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;
int M = 101;
int N = 101;
vector<vector<int>> LCS(M, vector<int>(N, 0));
vector<int> longestCommonSubsequence(vector<int> a, vector<int> b) {
  int m = a.size();
  int n = b.size();
  vector<int> result;
  for (int i = m - 1; i >= 0; i--) {
    for (int j = n - 1; j >= 0; j--) {
      if (a[i] == b[j])
        LCS[i][j] = 1 + LCS[i + 1][j + 1];
      else
        LCS[i][j] = max(LCS[i + 1][j], LCS[i][j + 1]);
    }
  }
  // print LCS table
  for (size_t i = 0; i <= m; i++) {
    for (size_t j = 0; j <= n; j++) {
      cout << LCS[i][j] << " ";
    }
    cout << endl;
  }

  // find the sub-sequence
  int i = 0, j = 0;
  vector<int> ss;
  while (i <= m && j <= n) {
    if (a[i] == b[j]) {
      result.push_back(a[i]);
      i++;
      j++;
    } else if (LCS[i + 1][j] > LCS[i][j + 1])
      j++;
    else
      j++;
  }

  cout << endl;

  return result;
}

int main() {
  vector<int> a = {1, 2, 3, 4, 1};
  vector<int> b = {3, 4, 1, 2, 1, 3};
  vector<int> result = longestCommonSubsequence(a, b);
  for (auto c : result) cout << c << " ";
  cout << endl;
  return 0;
}
3 3 3 2 2 1 0 
3 2 2 2 1 1 0 
3 2 1 1 1 1 0 
2 2 1 1 1 0 0 
1 1 1 1 1 0 0 
0 0 0 0 0 0 0 

1 2 3

References

Related Posts