Lcs prob. wrong ans ----------- https://ide.codingblocks.com/s/261189

#1
#2

Hi rahul i made a small change and it seems to work correct now
While printing LCS you should not check dp[i-1][j-1]+1==dp[i][j] … It does not work well for many cases like
abcdhghghghgfffhehhghghf
def

It gives output as df only

whereas when u only check if both i-1th and j-1th chars match just make i–,j–. That’s it.

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std ;




string lcs(string m,string n,int l1,int l2){
	int dp[100][100] ;
    string s1 = "";
	for(int i = 0 ; i <= l1 ; i++){
		for(int j = 0 ; j <= l2 ;j++){
			if(i==0 || j==0){
				dp[i][j] = 0 ;
			}

			else if(m[i-1] == n[j-1]){

				dp[i][j] = dp[i-1][j-1] + 1 ;
			}
			else{
				dp[i][j] = max(dp[i-1][j],dp[i][j-1]) ;
			}
		}
	}
    //cout<<dp[l1][l2]<<endl;
	int i = l1,j = l2 ;
    	while(j > 0 && i > 0){
    		
    			if(m[i-1] == n[j-1]){
    				s1 += m[i-1] ;
    			
    			j = j-1 ;
    			i = i-1 ;
    		}

    		else if(dp[i][j]  == dp[i-1][j]){
    			i = i-1 ;
    		}
    		else {
    			j = j-1 ;
    		}
    	}
    
	return s1 ;
}
int main(){
	string m,n ;
	cin >> m ;
	cin >> n ;
	int l1 = m.size() ;
	int l2 = n.size() ;

	string s  = lcs(m,n,l1,l2) ;
	cout << s ;
	int p = s.length() ; 
	for(int i = p ; i>=0;i--){
		cout << s[i] ;
	}
	return 0 ;
}