fork download
copy 
  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdlib>
  4. using namespace std;
  5.  
  6. /* Returns length of LCS for X[0..m-1], Y[0..n-1] */
  7. void lcs( char *X, char *Y, int m, int n )
  8. {
  9. 	   int L[m+1][n+1];
  10.  
  11.    	/* Following steps build L[m+1][n+1] in bottom up fashion. Note
  12.       	that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
  13.    	for (int i=0; i<=m; i++)
  14.    	{
  15.      	for (int j=0; j<=n; j++)
  16.      	{
  17.        		if (i == 0 || j == 0)
  18. 	         	L[i][j] = 0;
  19.        		else if (X[i-1] == Y[j-1])
  20.          		L[i][j] = L[i-1][j-1] + 1;
  21.        		else
  22.          		L[i][j] = max(L[i-1][j], L[i][j-1]);
  23.      	}
  24.    	}
  25.  
  26.    	// Following code is used to print LCS
  27.    	int index = L[m][n];
  28.  
  29.    	// Create a character array to store the lcs string
  30.    	char lcs[index+1];
  31.    	lcs[index] = '\0'; // Set the terminating character
  32.  
  33.    	// Start from the right-most-bottom-most corner and
  34.    	// one by one store characters in lcs[]
  35.    	int i = m, j = n;
  36.    	while (i > 0 && j > 0)
  37.    	{
  38.       	// If current character in X[] and Y are same, then
  39.       	// current character is part of LCS
  40.       	if (X[i-1] == Y[j-1])
  41.       	{
  42.           	lcs[index-1] = X[i-1]; // Put current character in result
  43.           	i--; j--; index--;     // reduce values of i, j and index
  44.       	}
  45.  
  46.       	// If not same, then find the larger of two and
  47.       	// go in the direction of larger value
  48.       	else if (L[i-1][j] > L[i][j-1])
  49.          	i--;
  50.       	else
  51.          	j--;
  52.    	}
  53.  
  54.    	// Print the lcs
  55.    	cout << "LCS of " << X << " and " << Y << " is " << lcs;
  56. }
  57.  
  58. int main()
  59. {
  60.   	char X[] = "AASDGX";
  61.   	char Y[] = "AAWD";
  62.  
  63.   	int m = strlen(X);
  64.   	int n = strlen(Y);
  65.  
  66.   	lcs(X, Y, m, n);
  67.  
  68.   	return 0;
  69. }
Success #stdin #stdout 0s 2684KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
LCS of AASDGX and AAWD is AAD
https://ideone.com/f5Hz1n
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 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!