,并无情地交给了你一个奇怪的任务——求最长非公共子序列,序列 a 是 b 的子序列,当且仅当从 b 中删除一些元素能得到 a,同理 "abcde","e" 和 空串都是 "abcde" 的子序列;的非公共子序列可能有很多,你只需要求出其中长度最长的非公共子序列的长度。
Lemon 丢给你两个字母序列 s_1 s 1 和 s_2 s 2 ,并无情地交给了你一个奇怪的任务——求最长非公共子序列。 序列 a 是 b 的子序列,当且仅当从 b 中删除一些元素(可以是零个或所有)能得到 a。 例如: 我们可以通过从 "abcde" 中删除 "b" 和 "d" 得到 "ace",因此 "ace" 是 "abcde" 的子序列。 同理 "abcde","e" 和 空串 都是 "abcde" 的子序列; 但 "abdc" 不是 "abcde" 的子序列。 序列 c 是 s_1 s 1 和 s_2 s 2 的非公共子序列当且仅当它满足以下条件中的任何一个: c 是 s_1 s 1 的子序列但不是 s_2 s 2 的子序列; c 是 s_2 s 2 的子序列但不是 s_1 s 1 的子序列。 s_1 s 1 和 s_2 s 2 的非公共子序列可能有很多,你只需要求出其中长度最长的非公共子序列的长度。
(图片来源网络,侵删)