LCS ALGORITHM ( example )

Question

There's a dynamic programming algorithm to find the Longest Common Subsequence of two sequences. How can I find the LCS algorithm of two sequences X and Y. (Test of correctness)

(a)   X  = ABEDFEESTYH  Y=ABEDFEESTYHABCDF

(b)  X =  BFAAAABBBBBJPRSTY  Y=ABCDEFGHIJKLMNOPRS

(c)  X = ϕ (Empty Sequence), Y = BABADCAB

Answer 1

EDIT: C++ implementation: http://comeoncodeon.wordpress.com/2009/08/07/longest-common-subsequence-lcs/

There's a dynamic programming algorithm to find the Longest Common Subsequence of two sequences (assuming that's what you meant by LCS): http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Here's the recurrence (from Wikipedia):

and the pseudocode (also from Wikipedia):

function LCSLength(X[1..m], Y[1..n])
    C = array(0..m, 0..n)
    for i := 0..m
       C[i,0] = 0
    for j := 0..n
       C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i] = Y[j]
                C[i,j] := C[i-1,j-1] + 1
            else:
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]

It's then possible to reconstruct what the longest subsequences are from the C array (see the Wikipedia article).