fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // define maximum length of sequence X and Y
  5. #define M 20
  6. #define N 20
  7.  
  8. // create a 2D-array to store solutions of subproblems
  9. // All its values will be initailzed by 0 by default 
  10. int lookup[M + 1][N + 1];
  11.  
  12. // Function to find length of Longest Common Subsequence of substring
  13. // X[0..m-1] and Y[0..n-1]
  14. int LCSLength(string X, string Y, int m, int n)
  15. {
  16.     // return if we have reached the end of either string
  17.     if (m == 0 || n == 0)
  18.         return 0;
  19.  
  20.     // if sub-problem is seen for the first time, solve it and 
  21.     // store its result in a array
  22.     if (lookup[m][n] == 0)
  23.     {
  24.         // if last character of X and Y matches
  25.         if (X[m - 1] == Y[n - 1])
  26.             lookup[m][n] = LCSLength(X, Y, m - 1, n - 1) + 1;
  27.  
  28.         else
  29.         // else if last character of X and Y don't match
  30.         lookup[m][n] = max(LCSLength(X, Y, m, n - 1), LCSLength(X, Y, m - 1, n));
  31.     }
  32.  
  33.     // return the subproblem solution from the array
  34.     return lookup[m][n];
  35. }
  36.  
  37. // main function
  38. int main()
  39. {
  40.     string X = "ABCBDAB", Y = "BDCABA";
  41.  
  42.     cout << "The length of LCS is " << LCSLength(X, Y, X.length(), Y.length());
  43.  
  44.     return 0;
  45. }
  46.  
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The length of LCS is 4
https://ideone.com/rZTKVS
Memoized solution to find length of LCS of two given sequences using an array
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!