题目描述
一个研究团队正在研究象形文字序列之间的相似性。他们将每个象形文字表示成一个非负整数。为了开展研究,他们采用了关于序列的如下概念。
对于一个给定的序列
下表给出了序列
子序列 | 由 |
---|---|
[3, 2, 1, 2] | 不移除任何元素。 |
[2, 1, 2] | [ |
[3, 2, 2] | [3, 2, |
[3, 2] | [3, |
[3] | [3, |
[ ] | [ |
另一方面,
考虑有两个象形文字序列
可以证明,任意两个序列
研究人员发现了两个象形文字序列
实现细节
你要实现以下函数。
std::vector<int> ucs(std::vector<int> A, std::vector<int> B)
:长度为 的数组,给出第一个序列。 :长度为 的数组,给出第二个序列。- 如果
和 有一个最全公共子序列,该函数应当返回一个包含该序列的数组。否则,该函数应当返回 (一个长度为 的数组,其唯一元素为 )。 - 对每个测试用例,该函数恰好被调用一次。
约束条件
- 对所有满足
的 ,都有 - 对所有满足
的 ,都有
子任务
子任务 | 分数 | 额外的约束条件 |
---|---|---|
1 | ||
2 | 对任意整数 |
|
3 | 对所有满足 |
|
4 | ||
5 | ||
6 | 没有额外的约束条件。 |
例子
例 1
考虑以下函数调用。
ucs([0, 0, 1, 0, 1, 2], [2, 0, 1, 0, 2])
此时,
由于
例 2
考虑以下函数调用。
ucs([0, 0, 2], [1, 1])
此时,
例 3
考虑以下函数调用。
ucs([0, 1, 0], [1, 0, 1])
此时,
评测程序示例
输入格式:
N M A[0] A[1] ... A[N-1] B[0] B[1] ... B[M-1]
输出格式:
T R[0] R[1] ... R[T-1]
这里 ucs
所返回的数组,而
时间限制:
空间限制: