【双指针5】判断子序列

题解

题目描述

给定两个整数序列 $a = a_1, a_2, \dots, a_n$ 和 $b = b_1, b_2, \dots, b_m$，判断序列 $a$ 是否是序列 $b$ 的子序列。

子序列的定义：一个序列通过从原序列中删除若干元素（可以不删除任何元素），且保持剩余元素的相对顺序不变而得到的序列。换句话说，序列 $a$ 是序列 $b$ 的子序列，当且仅当存在一个单调递增的索引序列 $i_1, i_2, \dots, i_n$ 满足 $1 \leq i_1 < i_2 < \dots < i_n \leq m$，且对于每个 $k$（$1 \leq k \leq n$），都有 $a_k = b_{i_k}$。

题目描述：

给定两个整数序列 $a = a_1, a_2, \dots, a_n$ 和 $b = b_1, b_2, \dots, b_m$，请你判断 $a$ 是否为 $b$ 的子序列。

子序列是指一个序列从原序列中删除一些元素（也可以不删除）后，剩下的元素的顺序保持不变。换句话说，序列 $a$ 是序列 $b$ 的子序列，当且仅当存在一个单调递增的索引序列 $i_1, i_2, \dots, i_n$ 满足 $1 \leq i_1 < i_2 < \dots < i_n \leq m$，且对于每个 $k \ (1 \leq k \leq n)$，都有 $a_k = b_{i_k}$。

你需要判断序列 $a$ 是否是序列 $b$ 的子序列。

输入

• 第一行输入两个整数 $n$ 和 $m$（$1 \leq n \leq m \leq 1000$），表示序列 $a$ 和序列 $b$ 的长度。
• 第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示序列 $a$。
• 第三行输入 $m$ 个整数 $b_1, b_2, \dots, b_m$，表示序列 $b$。

输出

如果序列 $a$ 是序列 $b$ 的子序列，输出 YES，否则输出 NO。

示例

输入 1

3 5
1 3 5
1 2 3 4 5

输出 1

YES

输入 2

3 5
1 3 6
1 2 3 4 5

输出 2

NO

样例1说明:

因为$a$数组$[1,3,5]$在$b$数组中对应的下标为$1,3,5$符合递增顺序且都能找到所以是其子序列