fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class LCS {
  5. public:
  6.   string longestLCS(string& s, string& t) {
  7.     int m = s.size();
  8.     int n = t.size();
  9.  
  10.     vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
  11.  
  12.     // Build DP table
  13.     for(int i = 1; i <= m; ++i) {
  14.       for(int j = 1; j <= n; ++j) {
  15.         if(s[i-1] == t[j-1])
  16.           dp[i][j] = 1 + dp[i-1][j-1];
  17.         else
  18.           dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
  19.       }
  20.     }
  21.  
  22.     // Backtrack to build LCS
  23.     int i = m, j = n;
  24.     string res = "";
  25.  
  26.     while(i > 0 && j > 0) {
  27.       if(s[i-1] == t[j-1]) {
  28.         res.push_back(s[i-1]);
  29.         i--; 
  30.         j--;
  31.       } else if(dp[i-1][j] > dp[i][j-1]) {
  32.         i--;
  33.       } else {
  34.         j--;
  35.       }
  36.     }
  37.  
  38.     reverse(res.begin(), res.end());
  39.     return res;
  40.   }
  41. };
  42.  
  43. int main() {
  44.   string s, t;
  45.   cin >> s >> t;
  46.   LCS obj;
  47.   cout << obj.longestLCS(s, t) << endl;
  48.   return 0;
  49. }
  50.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
abracadabra
avadakedavra
stdout
copy 
aaadara
https://ideone.com/eznLQ8
language:
C++ (gcc 8.3)
created:
4 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!