finding the longest common subsequence (lcs) of two strings:
ALGORITHM lcs(X,Y):
INPUT: strings X and Y with n and m elements, respectively
OUTPUT: for i = 0,..,n-1, j=0,..,m-1, the length L[i,j] of
the longest common subsequence of X[0..i] and Y[0..j]
FOR i <- -1 to n-1 DO
L[i,-1] <- 0
FOR j <- -1 to m-1 DO
L[-1,j] <- 0
FOR i <- 0 to n-1 DO
FOR j <- 0 to m-1 DO
IF X[i] = Y[j] THEN
L[i,j] <- L[i-1,j-1] + 1
ELSE
L[i,j] <- max{L[i-1,j],L[i,j-1]}
try:
A B C B D A B
B D C A B A