Print lcs..... 1 test case is getting failed

#1

#include
#include
using namespace std;
string lcs(string s1,string s2){
pair<int,int> dp[1003][1003];
string s="";
int n=s1.length();
int m=s2.length();

for(int i=0;i<=n;i++){
	for(int j=0;j<=m;j++){
        if(i==0){
			dp[0][j].first=0; dp[0][j].second=1;
		}
		if(j==0){
			dp[i][0].first=0; dp[i][0].second=2;
		}
		if(s1[i-1]==s2[j-1]){
			dp[i][j].first=dp[i-1][j-1].first+1;
            dp[i][j].second=3;
		}
		else{
			dp[i][j].first=max(dp[i-1][j].first,dp[i][j-1].first);
            dp[i][j].second=(dp[i][j].first==dp[i-1][j].first)?2:1;
		}
	}
}
     int r=n,t=m;
     while(r>0 && t>0){
         if(dp[r][t].second==1)
         t--;

         if(dp[r][t].second==2)
         r--;

         if(dp[r][t].second==3){
          s=s1[r-1]+s;
             r--;t--;
         }
     }

return s;
}
int main() {
string s1,s2;
cin>>s1>>s2;
string s=lcs(s1,s2);
s=="" ? cout<<" " : cout<<s;
return 0;
}

#2

please share ur approach of using a pair

the general LCS approach is

#3

in this i have made array of pair<int,int> in which the first element is for calculating the longest coomom subsequence length and the second element is used for keeping the track of the path for the lcs. In this 1 shows that leftward arrow is present and 2 represents arrow pointing towards top and 3 represents aroow in diagonal direction …
after filling the dp matrix ,i am travelling towards top from the rightmost bottom (with the help of the arrows )element to find the longest common subseq.

#4

your approach seems right
but the string being produced is not correct
like

for i/p
qwertyuioplmznchskalcmnbxghfjtklmnzxcbvnmjkanslpaoutrinvmakldkslqwertyuioplmznchskalcmnbxghfjtklmnzxcbvnmjkanslpaoutrinvmakldkslqwertyuioplmznchskalcmnbxghfjtklmnzxcbvnmjkanslpaoutrinvmakldkslqwertyuioplmznchskalcmnbxghfjtklmnzxcbvnmjkanslpao
lakdmshvndmxnvjrtyuiopqwertlakdmshvndmxnvjrtyuiopqwertdkslpensismfnvheksndertdkslpensismfnvheksndertdkslpensismfnvheksnd

ur o/p

lmshvnmnvrtyuioplmshvnmnvrtyuioplnsmnhknkslpinvkdksleismfnvkn

desired o/p

lakmvnmnvrtyuioplakmvnmnvrtyuioplnsmfnvksndksleimnhkntklmnvks
#5

Also for optimisation u do not have to store the arrow that u are traversing
go through the code i shared in the first comment u`ll understand it better

#6

i got stuck in the same input output and wanted to know why this code is not giving the desired output ,even though my approach seems to be right. :slight_smile:

#7

i would surely go through this code.

1 Like
#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.