6108 - 子序列(2)

题目描述

给定两个整数序列 AB,请判断序列 B 是否是序列 A 的一个子序列

一个序列 B 是序列 A 的子序列,当且仅当可以从 A 中删除若干个元素(也可以不删除),使得剩下的元素按照原有顺序恰好构成序列 B

需要注意:

  • 删除元素时,不能改变剩余元素的相对顺序
  • 子序列不要求连续,但必须保持顺序一致。

请你判断 B 是否为 A 的子序列。

输入

1 行读入两个整数 n, m,表示整数序列 AB 的长度。

2 行包含 n 个整数,表示序列 A

3 行包含 m 个整数,表示序列 B

输出

输出一行一个字符:

  • 如果 BA 的子序列,输出 Y
  • 否则输出 N
样例

输入

5 3
1 3 5 7 9
3 7 9

输出

Y

输入

5 3
1 3 5 7 9
3 9 7

输出

N

输入

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

输出

N
说明

样例说明 1

在序列 A 中选择第 2,4,5 个元素,得到序列:

3 7 9

与序列 B 完全一致,因此输出 Y

样例说明 2

虽然 39 都在序列 A 中,但在 A9 出现在 7 之后,无法保持顺序匹配,因此输出 N

数据范围

对于 50\% 的数据,保证 1 \le n, m \le 1000

对于 100\% 的数据,保证 1 \le n, m \le 10^5A B 序列中的元素的值,均在 [1,10^9] 范围内。

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 28
通过人数 23
金币数量 1 枚
难度 入门


上一题 下一题