Question

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 be the number of such longest common subsequences between A and B. Then x + 10y = ___.

Answer 1

To find the length of the longest common subsequence between two strings A and B, a dynamic programming approach can be used. The length of the longest common subsequence between A = "qpqrr" and B = "pqprqrp" is 3: "pqr". The count of longest common subsequences between A and B is 2.

Step-by-step explanation:

To find the length of the longest common subsequence between two strings A and B, we can use the concept of dynamic programming. We can create a matrix where each cell represents the length of the longest common subsequence up to that point in the strings. By filling in the matrix using the following conditions, we can find the length of the longest common subsequence:

1. If the characters from A and B at the current position are the same, we add 1 to the value of the cell diagonally above and to the left.
2. Otherwise, we take the maximum value between the cell above and the cell to the left.

In this case, the length of the longest common subsequence between A = "qpqrr" and B = "pqprqrp" is 3: "pqr".

To find the number of such longest common subsequences, we can use a similar dynamic programming approach. We create another matrix where each cell represents the count of longest common subsequences up to that point. We fill in the matrix using the same conditions as before and keep track of the count of subsequences. In this case, the count of longest common subsequences between A and B is 2.

Therefore, x + 10y = 3 + 10(2) = 23.