算法精解:最長公共子序列

最長公共子序列，英文縮寫為LCS（Longest Common Subsequence）。

其定義是，一個序列 S ，如果分别是兩個或多個已知序列的子序列，

且是所有符合此條件序列中最長的，則 S 稱為已知序列的最長公共子序列。

而最長公共子串(要求連續)和最長公共子序列是不同的

設序列 X 存儲在數組 x[m]中,序列 Y 存儲在數組 y[n]中, 二維數組 L[m+1][n+1]

存儲最長公共子序列的長度的疊代過程, S[ m + 1] [n + 1]存儲相應的狀态, 最長公共子

序列存儲在數組 z[ k]中

運作結果：

2

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 1 1

1 1 1 1 1 1 1 1 1 1

2 2 2 2 2 2 2 2 2 2