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)
```