source wikipedia
The table below shows the steps of generating LCS.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||
|---|---|---|---|---|---|---|---|---|---|
| Ø | M | Z | J | A | W | X | U | ||
| 0 | Ø | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | X | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 2 | M | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 3 | J | 0 | 1 | 1 | 2 | 2 | 2 | 2 | 2 |
| 4 | Y | 0 | 1 | 1 | 2 | 2 | 2 | 2 | 2 |
| 5 | A | 0 | 1 | 1 | 2 | 3 | 3 | 3 | 3 |
| 6 | U | 0 | 1 | 1 | 2 | 3 | 3 | 3 | 4 |
| 7 | Z | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 4 |
Here are the steps intepreted:
- given 2 strings: s1, s2, make them to char array:
char[] seq1 = s1.toCharArray();
char[] seq2 = s2.toCharArray();
int i = seq1.length;
int j = seq2.length;
- create 2 dimensional array using seq1, seq2:
char[][] matrix = new char[i][j]
- from tail to head, we do:
function lcs(matrix, seq1, seq2, i, j):
if i == 0 or j == 0: return " ";
else if seq1[i-1] == seq2[j-1]: return lcs(matrix, seq1, seq2, i, j) + seq1[i-1];
else:
if matrix[i][j-1] > matrix[i-1][j]: return lcs(matrix, seq1, seq2, i, j-1)
else lcs(matrix, seq1, seq2, i-1, j)