CSP-S 2023 第一轮 第7题：最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下：给定两个序列×=

题目

最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下：给定两个序列 $X={x_1,x_2,x_3,\cdots,x_m}$ 和 $Y={y_1,y_2,y_3,\cdots,y_n}$，最长公共子序列（LCS）问题的目标是找到一个最长的新序列 $Z={z_1,z_2,z_3,\cdots,z_k}$, 使得序列 $Z$ 既是序列 $X$ 的子序列，又是序列 $Y$ 的子序列，且序列 $Z$ 的长度 $k$ 在满足上述条件的序列里是最大的。
（注：序列 $A$ 是序列 $B$ 的子序列，当且仅当在保持序列 $B$ 元素顺序的情况下，从序列 $B$ 中删除若干个元素，可以使得剩余的元素构成序列 $A$。）则序列 ABCAAAABA 和 ABABCBABA 的最长公共子序列长度为（）

选项

• A. $4$
• B. $5$
• C. $6$
• D. $7$

答案

C

题解

答案是 C．6。

先找出一个长度为 6 的公共子序列：ABCABA。

• 在 ABCAAAABA 中，选第 1、2、3、4、8、9 个字符。
• 在 ABABCBABA 中，选第 1、2、5、7、8、9 个字符。

再说明为什么不可能达到 7：

两个序列的公共子序列最多包含 4 个 A、2 个 B、1 个 C，因此长度最多为 7。

若长度恰好为 7，就必须包含上述所有字符。但第二个序列的 4 个 A 中，有 2 个在 C 前面；而第一个序列在 C 前面只有 1 个 A，无法保持相同的先后顺序。

所以长度不可能为 7，最长公共子序列长度就是 6。