|
|
|
LCS-LENGTH(X, Y)
|
| 1 | m = length[X] |
| 2 | n = length[Y] |
| 3 | for i = 1 to m |
| 4 | do c[i, 0] = 0 |
| 5 | for j = 1 to n |
| 6 | do c[0, j] = 0 |
| 7 | for i = 1 to m |
| 8 | do for j = 1 to n |
| 9 | do if Xi == Yj |
| 10 | then c[i, j] = c[i-1, j-1] + 1 |
| 11 | b[i, j] = ARROW_CORNER |
| 12 | else if c[i-1, j] >= c[i, j-1] |
| 13 | then c[i, j]=c[i-1, j] |
| 14 | b[i, j] = ARROW_UP |
| 15 | else c[i, j]=c[i, j-1] |
| 16 | b[i, j] = ARROW_LEFT |
| 17 | return c and b |
|
| PRINT-LCS(b, X, i, j)
|
| 1 | if i=0 or j=0 |
| 2 | then return |
| 3 | if b[i, j] == ARROW_CORNER |
| 4 | then PRINT-LCS(b, X, i-1, j-1) |
| 5 | print Xi |
| 6 | elseif b[i, j] == ARROW_UP |
| 7 | then PRINT-LCS(b, X, i-1, j) |
| 8 | else PRINT-LCS(b, X, i, j-1) |
|
|