第08次上机实验题目（最长公共子序列问题）#

---

利用动态规划算法实现

最长公共子序列

问题描述#

给定一个序列，如果其中有些元素（也可能没有）被省略，则我们可以得到该序列的一个子序列。给定一个序列 $X = \langle x_1, x_2, \dots, x_n \rangle$，另一个序列 $Z$ 满足条件，存在严格递增索引序列 $I = \langle i_1, i_2, \dots, i_k \rangle$，使得对于所有 $j = 1, 2, \dots, k$，有 $x_{i_j} = z_j$，则称 $Z = \langle z_1, z_2, \dots, z_k \rangle$ 是 $X$ 的子序列。例如， $Z = \langle a, b, f, c \rangle$ 是 $X = \langle a, b, c, f, b, c \rangle$ 的子序列。

给定两个序列X和Y，问题是求出X和Y的最大长度公共子序列的长度。

输入格式#

两个给定字符串

输出格式#

两个序列最大长度公共子序列的长度。

样例输入#

abcfbc abfcab

样例输出#

4