Answer to Question #295413 in C++ for maple

Question

 need to write a dynamic program for solving the following problem.

 

1) input is two strings (sequences)

2) need to find longest non-consecutive common subsequence ( let us call it light common subsequence)

3) the sequences need to be read from left to right

4) the letters need not be alternating strictly but should not be consecutive

 

examples:

 

examples: - problem: 1 

correct_answer: 5 

s: "czdslvrqrutcalisavrieb" 

t: "fzprthfmovdtrijrxntc" 

- problem: 2 

correct_answer: 6

 s: "olfxisnyrwxereydrqgftyxpvuxnwp" 

t: "xkmnloaorrawywiubyregf" 

- problem: 3

 correct_answer: 4 

s: "xllmkgfnsyyxtlisthxiyjqryhulp" 

t: "yncwgapjocazejndvqrigphmtxkf"

Answer 1

#include <bits/stdc++.h>
using namespace std;






/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( char *X, char *Y, int m, int n )
{
	if (m == 0 || n == 0)
		return 0;
	if (X[m-1] == Y[n-1])
		return 1 + lcs(X, Y, m-1, n-1);
	else
		return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}






/* Driver code */
int main()
{


	 char str[100];
	 char *X;
	 char *Y;


    cout << "Enter the first sequence: ";
    cin >> X;
    cout << "Enter the second sequence: ";
    cin >> Y;
	
	int m = strlen(X);
	int n = strlen(Y);
	
	cout<<"Length of LCS is "<< lcs( X, Y, m, n ) ;
	
	return 0;
}