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 should take 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 must return the string corresponding the length found in 11cs [n] [m] and it should run in O (n + m) time where n is the length of x and m is the length of y.

Explanation / Answer

Longest Common Subsequence PseudoCode
-------------------------------------------------------------------------------------

Assuming we have the llcs[][] array., and x[n], and y[m] string.

length = llcs[n][m]

i = n

j = m

resultstring = "" //Empty string in start

while(i>0 && j >0){

if( x[i-1] ==y[j-1]){

//if character is same add in the start of the string

resultstring = x[i-1] + resultstring

}

// find largest of two llcs[i-1][j] and llcs[i][j-1] and move in the greatest string direction for maximum match

else if( llcs[i-1][j] > llcs[i][j-1] ) {

i--

}

else{

j--

}

}

print resultstring

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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