← 返回题目

题库练习子序列(2)

← 上一题下一题 →

A72008 | $子序列(2)$

来源编程题

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

给定两个整数序列 A 和 B ，请判断序列 B 是否是序列 A 的一个 子序列 。 一个序列 B 是序列 A 的子序列，当且仅当可以从 A 中删除若干个元素（也可以不删除），使得剩下的元素按照原有顺序恰好构成序列 B 。 需要注意： 删除元素时， 不能改变剩余元素的相对顺序 ； 子序列不要求连续，但必须保持顺序一致。 请你判断 B 是否为 A 的子序列。

输入格式

第 1 行读入两个整数 n, m ，表示整数序列 A 和 B 的长度。 第 2 行包含 n 个整数，表示序列 A 。 第 3 行包含 m 个整数，表示序列 B 。

输出格式

输出一行一个字符： 如果 B 是 A 的子序列，输出 Y 。 否则输出 N 。

输入输出样例

输入 #1

5 3
1 3 5 7 9
3 7 9

输出 #1

输入 #2

5 3
1 3 5 7 9
3 9 7

输出 #2

输入 #3

6 4
2 1 2 3 2 1
1 2 1 2

输出 #3

样例说明 1 在序列 A 中选择第 2,4,5 个元素，得到序列： 3 7 9 与序列 B 完全一致，因此输出 Y。 样例说明 2 虽然 3 和 9 都在序列 A 中，但在 A 中 9 出现在 7 之后，无法保持顺序匹配，因此输出 N。 数据范围 对于 50\% 的数据，保证 1 \le n, m \le 1000。 对于 100\% 的数据，保证 1 \le n, m \le 10^5，A B 序列中的元素的值，均在 [1,10^9] 范围内。

C++ 编辑器

输入

输出