Write a pseudocode description of the printLCS() algorithm, which prints the lon

Question

Write a pseudocode description of the printLCS() algorithm, which prints the longest common subsequence of two strings x and y. Your algorithm takes as input the completed 11cs [] [] integer array of longest common subsequence lengths, and the two strings x and y. (So, you do not have the path [] [] array - see Lecture 17, slides 98 and 99.) Your algorithm should start at llcs [n] [m] and work its way down to llcs [i] [j] where either i = 0 or j = 0 and it should run in 0(n + m) time where n is the length of x and m is the length of y.

Explanation / Answer

Takes X = < x_1,...x_m > and Y = < y_1,...y_n > as input. Stores c[i,j] into table c[0..m,0..n] in row-major order. The array b[i,j] points to the table entry for optimal subproblem solution when computing d[i,j].

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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