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

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 llcs [] [] 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

LOOP: i,j from n and m respectively to 0.

if(lcs[i][j-1]==lcs[i-1][j])

//include that character, this is because we have got that value from the diagonally positioned cell.

i--,j--;

else

move either to the cell lcs[i][j-1] or lcs[i-1][j] whichever value equals to lcs[i][j] and decrement the i or j value according.

here we dont inlcude that character.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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