若字符串 与字符串 的最长公共子序列(LCS)长度为 5,则( )。
A:它们的编辑距离为 5
B:它们至少有 5 个公共字符
C:它们最长公共子串长度为 5
D:它们一定长度相等
正确答案:B
答案解析
最长公共子序列(LCS)是指两个字符串中按顺序出现且字符相同的最长子序列,不要求连续。LCS长度为5表示存在5个字符在两个字符串中以相同顺序出现。编辑距离衡量通过插入、删除、替换操作将一个字符串转换为另一个的最少步数,与LCS无直接数值对应关系。公共字符数量至少等于LCS长度,因为LCS由实际存在的字符构成。最长公共子串要求字符连续,其长度小于或等于LCS长度,但不一定相等。字符串长度可以不同,LCS长度仅反映公共部分的顺序匹配程度,不约束总长度是否一致。
试卷来源:202603 CCF-GESP编程能力等级认证C++七级真题