Project ForgeWe wish to find the length of the longest common sub-sequence (LCS) of X[m] and Y[n] as l(m,n), where an incomplete recursive definition for the function l(i,j) is given below: l(i,j)=0 if either i=0 or j=0; = expr1, if i,j>0 and X[i-1]=Y[j-1]; = expr2, if i,j>0 and X[i-1]≠Y[j-1]. Which one of the following options is correct?
- Aexpr1 ≡ l(i-1,j)+1
- Bexpr1 ≡ l(i,j-1)
- expr2 ≡ max(l(i-1,j), l(i,j-1))
- Dexpr2 ≡ max(l(i-1,j-1), l(i,j))
Explanation
The standard LCS recurrence for the mismatch case (expr2) is max(l(i-1,j), l(i,j-1)) — matching option C exactly. (The match-case expr1 should be l(i-1,j-1)+1, which isn't offered as a labeled expr1 option here, so the question is really testing recognition of the correct mismatch formula.)
Source: GATE CS 2009 (2009)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.