#17. 判断子序列

判断子序列

给定一个长度为 nn 的整数序列 a1,a2,,ana_1,a_2,…,a_n 以及一个长度为 mm 的整数序列 b1,b2,,bmb_1,b_2,…,b_m

请你判断 aa 序列是否为 bb 序列的子序列。

子序列指序列的一部分项按原有次序排列而得的序列,例如序列 {a1,a3,a5}\{a_1,a_3,a_5\} 是序列 {a1,a2,a3,a4,a5}\{a_1,a_2,a_3,a_4,a_5\} 的一个子序列。

输入格式

第一行包含两个整数 n,mn,m

第二行包含 nn 个整数,表示 a1,a2,,ana_1,a_2,…,a_n

第三行包含 mm 个整数,表示 b1,b2,,bmb_1,b_2,…,b_m

输出格式

如果 aa 序列是 bb 序列的子序列,输出一行 Yes

否则,输出 No

数据范围

1nm1051 \le n \le m \le 10^5,
109ai,bi109-10^9 \le a_i,b_i \le 10^9

输入样例:

3 5
1 3 5
1 2 3 4 5

输出样例:

Yes

样例:基础正确用例(典型子序列)。

n=m 完全相同:必须输出 Yes;卡把“子序列”误当“真子串/必须跳过元素”的错误。

n=m 仅一项不同:卡只比较长度/只比前几项/漏检最后差异。

n=1 且 b 中多次出现:卡只检查一次、或错误地要求“连续出现”。

n=1 且 b 中不存在:基础反例;卡默认输出 Yes/未找到也算找到。

顺序不一致(a 元素都在 b 里但次序不对):卡把“子序列”写成“子集/只看出现次数”。

a 有大量重复但 b 次数不够:卡只判断“值出现过”而不计数/不推进指针。

a 重复且 b 次数刚好够且分散:卡错误地要求连续、或匹配策略不正确。

全负数正确匹配:卡把负数处理错(比如用 unsigned、或读入/比较错误)。

负数混合且缺项:卡“只要前面能匹配就认为 Yes”、或漏判中间元素。

a 是 b 的前缀:卡一些写法只会在中间跳而不会处理前缀/边界。

a 是 b 的后缀:卡没扫到末尾/提前结束。

必须用到 b 的最后一个元素才能匹配:重点卡“扫描 b 没到最后”“循环条件写错(i<n && j<m 之类)”。

几乎全匹配,只缺一个中间元素(n 接近 m):卡 off-by-one、指针推进错导致漏匹配。

极值 -1e9 与 1e9:卡 int 溢出/比较边界(虽一般 int 足够,但有些语言/写法会出错)。

同极值但顺序相反:卡把“集合匹配”当“序列匹配”。

交替重复序列(需要贪心地从左到右选):卡错误回退/错误地“匹配后不推进”导致乱序。

元素及次数看似够,但顺序导致不可能:卡只看计数不看相对顺序。

m 很大、n 很小、匹配点很稀疏且包含最后位置:卡性能(O(nm) 会慢)、以及“必须扫到接近末尾”。

与 19 类似但最后一个目标不存在:卡“找到前几个就直接 Yes”、或末尾漏判。

最小规模 n=m=1 且相等:卡边界初始化/循环不进导致错误输出。

最小规模 n=m=1 且不等:卡边界判断反例。

b 单调下降,a 单调上升:卡一些错误假设(比如以为有序就能二分/误用双指针方向)。

b 重复很多,a 需要选择“合适的后续重复”才能成功:卡“总是匹配到错误位置后无法继续”的非标准写法(正确双指针没问题)。

与 24 同 b,但 a 顺序换一下变成不可能:卡“只要值都出现过就 Yes”、以及不正确的匹配策略。