CMI-2021-Data Science

Question

There are two longest subsequences, not necessarily contiguous, common to the strings “ARTIFICIAL” and “INTELLIGENCE”. They are “IIC” and “TIC” which are of length three.

Consider two strings S1 = “CORONAVIRUS” and S2 = “SARSCOVID”. Let x be the length of a longest common subsequence between S1 and S2 and let y be the number of such longest common subsequences of length x between S1 and S2. What is x + 5y?

 

• A. 13
• B. 14
• C. 15
• D. 16

Answer 1

1)CORONAVIRUS

SARSCOVID

 

2)  CORONA VI RUS

SARSCOVID

There are 2 possible longest subsequence with length 4.

Hence. 4+2*5

14

Ans) option B

Answer 2

looking at any one string say coronavirus from right to left, look for common substrings;

we get , rovi and covi. so x=4, and y=2;

ans = 14