Trying to figure out part B. For part A, I defined the entry was T(i, j) that re

Question

Trying to figure out part B.

For part A, I defined the entry was T(i, j) that returns the length of the longest string per the above constraints of two smaller strings of X and Y going to xi and yj.

For part B, I am trying to determine what T(i, j) means and I have two cases: where the ith character in x equals the jth character of y, then I take the max of T(i - 1, j) or T(i, j - 1) or 1 + T(i - 1, j - 1).

and where the ith and jth characters are not the same, in which I take the max of T(i - 1, j) or T(i, j - 1).

Is this correct?

Given two strings X = zi,Zg, ,Fn and Y-yi,Y2, , ym, give a dynamic programming algorithm to find the length k of the longest string Z 21,... , 2k where Z appears as a substring of X and as a subsequence of Y. Recall that a substring has consecutive elements For example, consider the following input: Xa, b, d, b, a,b, f.g,d Y-b,e,t,f,d, b, f,a, f,r For this input, the answer is 4 since b, d, b, a is a substring of X and it is also a subsequence of Y For simplicity, you can assume that all table entries use O(1) space. You do not need to output the actual substring, just its length. Faster (and correct) asymptotic running time is worth more credit (a) Define the entries of your table in words. For example, T(i) or T(i,j) is... (b) State the recurrence for entries of table in terms of smaller subproblems

Explanation / Answer

Recursive Formulation :

Case 1: If xi = yj , then zk = xi = yj and Zk1 is a LCS of X and Y ending at xi1 and yj1

Recursive Formulation :

Case 1: If xi = yj , then zk = xi = yj and Zk1 is a LCS of X and Y ending at xi1 and yj1 Case 2: If xi 6= yj , then there can’t be a common substring ending at xi and yj

Recursive Formulation :

Case 1: If xi = yj , then zk = xi = yj and Zk1 is a LCS of X and Y ending at xi1 and yj1 Case 2: If xi 6= yj , then there can’t be a common substring ending at xi and yj! di,j = di1,j1 + 1 if xi = yj 0 if xi 6= yj

Recursive Formulation :

Case 1: If xi = yj , then zk = xi = yj and Zk1 is a LCS of X and Y ending at xi1 and yj1 Case 2: If xi 6= yj , then there can’t be a common substring ending at xi and yj! di,j = di1,j1 + 1 if xi = yj 0 if xi 6= yj Finally, we can find length of longest common substring by finding maximum di,j among all possible ending positions i and j. LCSubString(X, Y ) = max{di,j}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.