fork(2) download
copy 
  1. //
  2. //  main.cpp
  3. //  Finding Longest Common Subsequence
  4. //
  5. //  Created by Himanshu on 14/06/24.
  6. //
  7.  
  8. #include <iostream>
  9. #include <vector>
  10. #include <string>
  11. using namespace std;
  12.  
  13. void printLCSTable(const int m, const int n, vector<vector<int>> dp) {
  14.  
  15.     for (int i = 0; i <= m; i++) {
  16.         for (int j = 0; j <= n; j++) {
  17.             cout << dp[i][j] << " ";
  18.         }
  19.  
  20.         cout<<endl;
  21.     }
  22. }
  23.  
  24. vector<vector<int>> LCSTable(const string& X, const string& Y) {
  25.  
  26.     int m = (int) X.length();
  27.     int n = (int) Y.length();
  28.  
  29.     vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
  30.  
  31.     for (int i = 1; i <= m; i++) {
  32.         for (int j = 1; j <= n; j++) {
  33.             if (X[i - 1] == Y[j - 1]) {
  34.                 dp[i][j] = dp[i - 1][j - 1] + 1;
  35.             } else {
  36.                 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
  37.             }
  38.         }
  39.     }
  40.  
  41.     return dp;
  42. }
  43.  
  44. string findLCS(const string& X, const string& Y, const vector<vector<int>>& dp) {
  45.  
  46.     int i = (int) X.length();
  47.     int j = (int) Y.length();
  48.     string lcs;
  49.  
  50.     while (i > 0 && j > 0) {
  51.  
  52.         cout << "X: " << X[i-1] << ", Y: " << Y[j-1] << "; i: " << i << ", j: " << j << endl;
  53.  
  54.         if (X[i - 1] == Y[j - 1]) {
  55.             lcs = X[i - 1] + lcs; // Add this character to the LCS
  56.             i--;
  57.             j--;
  58.         } else if (dp[i - 1][j] > dp[i][j - 1]) {
  59.             i--;      // Move Up
  60.         } else {
  61.             j--;      // Move Left
  62.         }
  63.     }
  64.  
  65.     return lcs;
  66. }
  67.  
  68. int main() {
  69.  
  70.     string X = "ATDBM";
  71.     string Y = "BATCB";
  72.  
  73.     vector<vector<int>> dp = LCSTable(X, Y);
  74.  
  75.     string lcs = findLCS(X, Y, dp);
  76.  
  77.     cout << "The Longest Common Subsequence is: " << lcs << endl << endl;
  78.  
  79.     cout<<"LCS Table"<<endl;
  80.     printLCSTable((int) X.size(), (int) Y.size(), dp);
  81.  
  82.     return 0;
  83. }
  84.  
Success #stdin #stdout 0.01s 5244KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
X: M, Y: B; i: 5, j: 5
X: B, Y: B; i: 4, j: 5
X: D, Y: C; i: 3, j: 4
X: D, Y: T; i: 3, j: 3
X: T, Y: T; i: 2, j: 3
X: A, Y: A; i: 1, j: 2
The Longest Common Subsequence is: ATB

LCS Table
0 0 0 0 0 0 
0 0 1 1 1 1 
0 0 1 2 2 2 
0 0 1 2 2 2 
0 1 1 2 2 3 
0 1 1 2 2 3
https://ideone.com/BesOhU
language:
C++14 (gcc 8.3)
created:
130 days 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!