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