fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. string getLCS(string X, string Y) {
  8.     int m = X.length(), n = Y.length();
  9.     vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
  10.  
  11.     // Build dp table
  12.     for (int i = 1; i <= m; ++i) {
  13.         for (int j = 1; j <= n; ++j) {
  14.             if (X[i - 1] == Y[j - 1])
  15.                 dp[i][j] = 1 + dp[i - 1][j - 1];
  16.             else
  17.                 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
  18.         }
  19.     }
  20.  
  21.     // Backtrack to find the LCS string
  22.     string lcs = "";
  23.     int i = m, j = n;
  24.     while (i > 0 && j > 0) {
  25.         if (X[i - 1] == Y[j - 1]) {
  26.             lcs = X[i - 1] + lcs;
  27.             --i; --j;
  28.         } else if (dp[i - 1][j] > dp[i][j - 1]) {
  29.             --i;
  30.         } else {
  31.             --j;
  32.         }
  33.     }
  34.  
  35.     return lcs;
  36. }
  37.  
  38. int main() {
  39.     string str1 = "ABCBDAB";
  40.     string str2 = "BDCAB";
  41.     string lcs = getLCS(str1, str2);
  42.     cout << "Length of LCS: " << lcs.length() << endl;
  43.     cout << "LCS: " << lcs << endl;
  44.     return 0;
  45. }
  46.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Length of LCS: 4
LCS: BDAB
https://ideone.com/zHfwzm
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

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!