fork download
copy 
  1. // The longest common subsequence in C++
  2.  
  3. #include <iostream>
  4. #include <cstring>
  5.  
  6. using namespace std;
  7.  
  8. void lcsAlgo(char *S1, char *S2, int m, int n) {
  9.   int LCS_table[m + 1][n + 1];
  10.  
  11.  
  12.   // Building the mtrix in bottom-up way
  13.   for (int i = 0; i <= m; i++) {
  14.     for (int j = 0; j <= n; j++) {
  15.       if (i == 0 || j == 0)
  16.         LCS_table[i][j] = 0;
  17.       else if (S1[i - 1] == S2[j - 1])
  18.         LCS_table[i][j] = LCS_table[i - 1][j - 1] + 1;
  19.       else
  20.         LCS_table[i][j] = max(LCS_table[i - 1][j], LCS_table[i][j - 1]);
  21.     }
  22.   }
  23.  
  24.   int index = LCS_table[m][n];
  25.   char lcsAlgo[index + 1];
  26.   lcsAlgo[index] = '\0';
  27.  
  28.   int i = m, j = n;
  29.   while (i > 0 && j > 0) {
  30.     if (S1[i - 1] == S2[j - 1]) {
  31.       lcsAlgo[index - 1] = S1[i - 1];
  32.       i--;
  33.       j--;
  34.       index--;
  35.     }
  36.  
  37.     else if (LCS_table[i - 1][j] > LCS_table[i][j - 1])
  38.       i--;
  39.     else
  40.       j--;
  41.   }
  42.  
  43.   // Printing the sub sequences
  44.   cout << "S1 : " << S1 << "\nS2 : " << S2 << "\nLCS: " << lcsAlgo << "\n";
  45. }
  46.  
  47. int main() {
  48.   char S1[] = "ACADB";
  49.   char S2[] = "CBDA";
  50.   int m = strlen(S1);
  51.   int n = strlen(S2);
  52.  
  53.   lcsAlgo(S1, S2, m, n);
  54. }
Success #stdin #stdout 0.01s 5360KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
S1 : ACADB
S2 : CBDA
LCS: CB
https://ideone.com/tv5Ms7
longest common subsequence for Strings
language:
C++ (gcc 8.3)
created:
1 year 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!