Gateforum-dynamic programming-longest common subsequence

Question

Consider two strings A="pqqrr" and B="pqprqrp",let x be the length of the longest sub-sequence between A and B and let y be the number of such common sub-sequences between A and B then 2x+4y= ?

A) 22          B) 20          C)18          D)24

The answer is B) i.e. x=4 and y=3. I have understood how x is equal to 4. But what are the common sub-sequences? I am getting two i.e. "pqqr" and "pqrr". Here I have one doubt. Do i have to count twice for "pqqr" in A? Once for "pqqrr" and another one for "pqqrr".

Comments

If duplicates are allowed you will get 8 LCS

1. pqqr
2. pqqr
3. pqrr
4. pqrr
5. pqqr
6. pqqr
7. pqrr
8. pqrr

---

WITH DUPLICATES:-

1st character = {p}

2nd character = {q,q}

3rd character = {q,r}

4th character = {r,r}

Total possible LCS = 1*2*2*2 =8

WITHOUT DUPLICATES:-

1st character = {p}

2nd character = {q}

3rd character = {q,r}

4th character = {r}

Total possible LCS = 1*1*2*1 =2

Thus, y=2 (without duplicates)

---

@Balaji Jegan ,@MiNiPanda

see this

https://gateoverflow.in/1996/gate2014-2-37