fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string longestCommonSubsequence(const string& X, const string& Y) {
  4.     int m = X.size();
  5.     int n = Y.size();
  6.     vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
  7.     for (int i = 1; i <= m; i++) {
  8.         for (int j = 1; j <= n; j++) {
  9.             if (X[i - 1] == Y[j - 1]) {
  10.                 dp[i][j] = dp[i - 1][j - 1] + 1;
  11.             } else {
  12.                 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
  13.             }
  14.         }
  15.     }
  16.     string lcs;
  17.     int i = m, j = n;
  18.     while (i > 0 && j > 0) {
  19.         if (X[i - 1] == Y[j - 1]) {
  20.             lcs += X[i - 1];
  21.             --i;
  22.             --j;
  23.         } else if (dp[i - 1][j] > dp[i][j - 1]) {
  24.             --i;
  25.         } else {
  26.             --j;
  27.         }
  28.     }
  29.  
  30.     reverse(lcs.begin(), lcs.end());
  31.     return lcs;
  32. }
  33.  
  34. int main() {
  35.     string X, Y;
  36.     cout << "Enter first string: ";
  37.     cin >> X;
  38.     cout << "Enter second string: ";
  39.     cin >> Y;
  40.  
  41.     string lcs = longestCommonSubsequence(X, Y);
  42.     cout << "Length of LCS: " << lcs.length() << endl;
  43.     cout << "LCS: " << lcs << endl;
  44.  
  45.     return 0;
  46. }
  47.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Enter first string: Enter second string: Length of LCS: 0
LCS:
https://ideone.com/dTtBBZ
language:
C++ (gcc 8.3)
created:
8 hours 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!