fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std; 
  4.  
  5.  
  6.  
  7. int max(int a, int b);  
  8.  
  9.  
  10. /* Returns length of LCS for X[0..m-1], Y[0..n-1] */
  11.  
  12. int lcs( char *X, char *Y, int m, int n )  
  13. {  
  14.  
  15.     if (m == 0 || n == 0)  
  16.  
  17.         return 0;  
  18.  
  19.     if (X[m-1] == Y[n-1])  
  20.  
  21.         return 1 + lcs(X, Y, m-1, n-1);  
  22.  
  23.     else
  24.  
  25.         return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));  
  26. }  
  27.  
  28.  
  29. /* Utility function to get max of 2 integers */
  30.  
  31. int max(int a, int b)  
  32. {  
  33.  
  34.     return (a > b)? a : b;  
  35. }  
  36.  
  37.  
  38. /* Driver code */
  39.  
  40. int main()  
  41. {  
  42.  
  43.     char X[] = "BXGTAB";  
  44.  
  45.     char Y[] = "GXTXAYB";  
  46.  
  47.  
  48.  
  49.     int m = strlen(X);  
  50.  
  51.     int n = strlen(Y);  
  52.  
  53.  
  54.  
  55.     cout<<"Length of LCS is "<< lcs( X, Y, m, n ) ;  
  56.  
  57.  
  58.  
  59.     return 0;  
  60. }
Success #stdin #stdout 0s 4504KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Length of LCS is 4
https://ideone.com/qLA5Da
language:
C++14 (clang 8.0)
created:
3 years 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!