fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. string s1, s2;
  4. int dp[1000][1000];
  5. int m, n;
  6. int LCS(int i, int j)
  7. {
  8. if (i == m || j == n)
  9.  return 0;
  10.  if (dp[i][j] != -1) 
  11. return dp[i][j];
  12.   if (s1[i] == s2[j])
  13.  return dp[i][j] = 1 + LCS(i + 1, j + 1);
  14.    else
  15. {
  16. int res1=LCS(i+1,j);
  17. int res2=LCS(i,j+1);
  18.   return dp[i][j]= max(res1,res2);
  19. }
  20. }
  21.  
  22.  
  23. string buildLCS(int i, int j) 
  24. {
  25.     if (i == m || j == n) 
  26. return "";
  27. if (s1[i] == s2[j]) 
  28. {
  29. return s1[i] +buildLCS(i + 1, j + 1);
  30.     } 
  31. else 
  32. {
  33.  if (dp[i + 1][j] > dp[i][j + 1])
  34.    return buildLCS(i + 1, j);
  35.  else
  36. return buildLCS(i, j + 1);
  37.     }
  38. }
  39.  
  40. int main()
  41.  {
  42.   cin >> s1 >> s2;
  43.   m = s1.size();
  44.   n = s2.size();
  45.   for (int i = 0; i <= m; i++) 
  46. {
  47.   for (int j = 0; j <= n; j++) 
  48. {
  49.    dp[i][j] = -1;
  50.         }
  51.     }
  52.  
  53.     int length = LCS(0, 0);
  54.     string lcsString =buildLCS(0, 0);
  55.  
  56.     cout<< length << endl;
  57.     cout <<lcsString << endl;
  58.  
  59.     return 0;
  60. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
abcd
bc
stdout
copy 
2
bc
https://ideone.com/3KN50y
language:
C++ (gcc 8.3)
created:
19 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!