fork download
copy 
  1.  #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. string LCS(const string &a, const string &b) {
  5.     int n = a.size();
  6.     int m = b.size();
  7.     vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
  8.     for (int i = 1; i <= n; i++) {
  9.         for (int j = 1; j <= m; j++) {
  10.             if (a[i - 1] == b[j - 1]) {
  11.                 dp[i][j] = dp[i - 1][j - 1] + 1;
  12.             } else {
  13.                 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
  14.             }
  15.         }
  16.     }
  17.     string s;
  18.     int i = n, j = m;
  19.     while (i > 0 && j > 0) {
  20.         if (a[i - 1] == b[j - 1]) {
  21.             s = a[i - 1] + s;
  22.             i--;
  23.             j--;
  24.         } else if (dp[i - 1][j] > dp[i][j - 1]) {
  25.             i--;
  26.         } else {
  27.             j--;
  28.         }
  29.     }
  30.     return s;
  31. }
  32.  
  33.  
  34.  
  35. int main() {
  36.     string s1, s2;
  37.     cin >> s1;
  38.     cin >> s2;
  39.     cout << LCS(s1, s2);
  40.     return 0;
  41. }
  42.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MSUni7
language:
C++14 (clang 8.0)
created:
3 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!