题目描述
- 给定一个长度为n的整数序列
a1,a2,…,an以及一个长度为m的整数序列b1,b2,…,bm。请你判断a序列是否为b序列的子序列。 - 子序列指序列的一部分项按原有次序排列而得的序列，例如序列
{a1,a3,a5}是序列{a1,a2,a3,a4,a5}的一个子序列。
输入格式
- 第一行包含两个整数
n,m。 - 第二行包含
n个整数，表示a1,a2,…,an。 - 第三行包含
m个整数，表示b1,b2,…,bm。
输出格式
- 如果
a序列是b序列的子序列，输出一行Yes。否则，输出No。
数据范围
1 ≤ n ≤ m ≤10^5,−10^9 ≤ ai,bi ≤ 10^9
基本思路
- 输入方面，首先是两个整数，整数的最大值为十万，因此可以使用基本整型
int来进行表示。接着输入两个数组，数组中元素的最大值为十亿，因此仍然可以通过基本整型int来进行表示。所以，最终可以通过创建两个单元数为100010的整型数组分别记录a和b。 - 输出方面，只需要判定
a数组是不是b数组的子序列即可。 - 过程处理方面，只需要按照a数组中的元素顺序，从前到后遍历b数组，检查其中是否存在这样一个序列即可，较为简单。
实现代码
#include <cstdio>
const int N = 100010;
int a[N], b[N];
bool is_son(const int &n, const int &m)
{
int ap, bp;
for(bp = 0, ap = 0; bp < m && ap != n; ++bp) if(b[bp] == a[ap]) ap++;
if(ap == n) return true;
else return false;
}
int main(void)
{
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < n; ++i) scanf("%d", &a[i]);
for(int i = 0; i < m; ++i) scanf("%d", &b[i]);
if(is_son(n, m)) printf("Yes");
else printf("No");
return 0;
}
