Longest Common Subsequence
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 c[i,j]
.
LCS-Length(X, Y)
m <- length[X]
n <- length[Y]
for i <- 1 to m
c[i,0] <- 0
for j <- 1 to n
c[0,j] <- 0
for i <- 1 to m
for j <- 1 to n
if (x_i == y_j) {
c[i,j] <- c[i-1,j-1] + 1
b[i,j] <- NW
}
else if (c[i-1,j] >= c[i,j-1]) {
c[i,j] <- c[i-1,j]
b[i,j] <- N
}
else {
c[i,j] <- c[i,j-1]
b[i,j] <- W
}
Up to CS 3158 home page