fork download
copy 
  1. //
  2. //  main.cpp
  3. //  Longest Common Subsequence
  4. //
  5. //  Created by Himanshu on 17/09/21.
  6. //
  7.  
  8. #include <iostream>
  9.  
  10. #include <iostream>
  11. using namespace std;
  12.  
  13. void LCS (string s1, string s2) {
  14.     int N = (int)s1.size(), M = (int)s2.size();
  15.     int L[N+1][M+1];
  16.  
  17.     for (int i=0; i<=N; i++) {
  18.         for (int j=0; j<=M; j++) {
  19.             L[i][j] = 0;
  20.         }
  21.     }
  22.  
  23.     for (int i=0; i<=N; i++) {
  24.         for (int j=0; j<=M; j++) {
  25.             if (i == 0 || j == 0) {
  26.                 L[i][j] = 0;
  27.             } else if (s1[i-1] == s2[j-1]) {
  28.                 L[i][j] = L[i-1][j-1] + 1;
  29.             } else {
  30.                 L[i][j] = max(L[i][j-1], L[i-1][j]);
  31.             }
  32.         }
  33.     }
  34.  
  35.     cout<<"Length of Longest Common Subsequence (LCS) is: "<<L[N][M]<<endl;
  36.  
  37. }
  38.  
  39. int main() {
  40.     string s1 = "abcde", s2 = "ace";
  41.     LCS(s1, s2);
  42. }
  43.  
Success #stdin #stdout 0.01s 5392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Length of Longest Common Subsequence (LCS) is: 3
https://ideone.com/iUYaWt
language:
C++ 4.3.2 (gcc-4.3.2)
created:
3 years 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!