A dynamic programming approach of longest-common subsequence(LCS) is given below

The book gives an algorithm in pseudo code to construct a LCS, as shown below

Describe an algortihm in pseudocode that enumerates ALL longest common subsequences of two sequences X and Y .

LCS-LENGTH(X,Y) 1 m = X.length 2 n = Y.length 3 let b[1..m, 1..n] and c[O..m, 0..n] be new tables 4 for i = 1 to m 5 c[i,0] = 0 6 for j = 0 ton 7 c[0,j] = 0 8 for i = 1 to m for j = 1 to n if Xi == Y; c[i, j] = c[i 1, j - 1] + 1 b[i, j] = " " elseif c[i 1, j] > c[i, j - 1] 14 c[i, j] = c[i 1, j] b[i, j] = "p1" 16 else c[i, j] = c[i, j - 1] 17 b[i, j] = " " 18 return c and b 10 13 PRINT-LCS(b,X,i,j) 1 if i == 0 or j == 0) 2 return 3 if b[i, j] == T 4 PRINT-LCS(6, X, i -1, j - 1) 5 print xi 6 elseif b[i, j] == "p." 7 PRINT-LCS(6,X, i 1,j) 8 else PRINT-LCS(b, X, i, j - 1) LCS-LENGTH(X,Y) 1 m = X.length 2 n = Y.length 3 let b[1..m, 1..n] and c[O..m, 0..n] be new tables 4 for i = 1 to m 5 c[i,0] = 0 6 for j = 0 ton 7 c[0,j] = 0 8 for i = 1 to m for j = 1 to n if Xi == Y; c[i, j] = c[i 1, j - 1] + 1 b[i, j] = " " elseif c[i 1, j] > c[i, j - 1] 14 c[i, j] = c[i 1, j] b[i, j] = "p1" 16 else c[i, j] = c[i, j - 1] 17 b[i, j] = " " 18 return c and b 10 13 PRINT-LCS(b,X,i,j) 1 if i == 0 or j == 0) 2 return 3 if b[i, j] == T 4 PRINT-LCS(6, X, i -1, j - 1) 5 print xi 6 elseif b[i, j] == "p." 7 PRINT-LCS(6,X, i 1,j) 8 else PRINT-LCS(b, X, i, j - 1)