45 votes 45 votes Consider two strings $A$="qpqrr" and $B$="pqprqrp". Let $x$ be the length of the longest common subsequence (not necessarily contiguous) between $A$ and $B$ and let $y$ be the number of such longest common subsequences between $A$ and $B$. Then $x +10y=$ ___. Algorithms gatecse-2014-set2 algorithms normal numerical-answers dynamic-programming + – go_editor asked Sep 28, 2014 • retagged Jul 3, 2017 by Silpa go_editor 17.0k views answer comment Share Follow See 1 comment See all 1 1 comment reply Naveen Kumar 3 commented Sep 20, 2018 reply Follow Share LCS of length 4 ==> x=4 LCS={qpqr,qprr,pqrr} ==>y=3 x+4y=34. 8 votes 8 votes Please log in or register to add a comment.
2 votes 2 votes common subsequences in A and B are qpqr , pqrr , qprr so X=4 and Y=3 4 +10*3 =34 Sanket_ answered Aug 15, 2016 Sanket_ comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes How to calculate the number of largest common subsequences..? dhingrak answered Jan 18, 2015 dhingrak comment Share Follow See all 3 Comments See all 3 3 Comments reply Abhishek Singh 2 commented Oct 16, 2016 i edited by Abhishek Singh 2 Oct 16, 2016 reply Follow Share https://www.youtube.com/watch?v=NnD96abizww Go to above given link This will help you to calculate longest sub sequences by drawing a table and from there it will be easier for you to figure out number of longest subsequence 4 votes 4 votes VS commented Jun 17, 2017 reply Follow Share @Abhishek video is fine . But, still how to find the number of LCSs ?? 0 votes 0 votes rahul sharma 5 commented Dec 11, 2017 reply Follow Share @VS.Check my answer.It might give a little help 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes I got the answer while doing like this at the first attempt. Is this a valid method. Rohitburke answered Jan 10, 2021 Rohitburke comment Share Follow See all 0 reply Please log in or register to add a comment.