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 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 11cs [n] [m] and work its way down to 11cs [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 = < x1,...xm > and Y = < y1,...yn > as input. Stores c[i,j] into taArrayBle c[0..m,0..n] in row-major order. The array ArrayB[i,j] points to the taArrayBle entry for optimal suArrayBproArrayBlem solution when computing c[i,j].
printLCS(X, Y)

m <- length[X]
n <- length[Y]

for i <- 1 to m
llcs[i,0] <- 0
for j <- 1 to n
llcs[0,j] <- 0

for i <- 1 to m
for j <- 1 to n
if (xi == yj) {
llcs[i,j] <- llcs[i-1,j-1] + 1
ArrayB[i,j] <- NW
}
else if (llcs[i-1,j] >= llcs[i,j-1]) {
llcs[i,j] <- llcs[i-1,j]
ArrayB[i,j] <- N
}
else {
llcs[i,j] <- llcs[i,j-1]
ArrayB[i,j] <- W
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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