← 返回题目列表

Codeforces · 1553/D

D. 退格键

中文机器翻译题面 查看原题

给定两个字符串 $$$s$$$ 和 $$$t$$$,均由小写英文字母组成。您将逐个字符地输入字符串 $$$s$$$,从第一个字符到最后一个字符。

输入字符时,您可以按“退格”按钮,而不是按与其对应的按钮。它会删除尚未删除的字符中您输入的最后一个字符(或者如果当前字符串中没有字符则不执行任何操作)。例如,如果 $$$s$$$ 是“abcbd”,并且按 Backspace 键而不是键入第一个和第四个字符,您将得到字符串“bd”(第一次按 Backspace 键不会删除任何字符,第二次按 Backspace 键会删除字符“c”)。另一个示例,如果 $$$s$$$ 是“abcaa”并且您按 Backspace 而不是最后两个字母,则结果文本是“a”。

你的任务是确定如果你输入字符串$$$s$$$并按“Backspace”而不是输入$$$s$$$的几个(可能是零个)字符,是否可以获得字符串$$$t$$$。

输入

第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^5$$$) — 测试用例的数量。

每个测试用例的第一行包含字符串 $$$s$$$ ($$$1 \le |s| \le 10^5$$$)。 $$$s$$$的每个字符都是一个小写英文字母。

每个测试用例的第二行包含字符串 $$$t$$$ ($$$1 \le |t| \le 10^5$$$)。 $$$t$$$的每个字符都是小写英文字母。

保证所有测试用例的字符串中的字符总数不超过$$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果可以通过键入字符串 $$$s$$$ 并按“Backspace”按钮替换一些字符来获取字符串 $$$t$$$,则打印“YES”,如果不能,则打印“NO”。

您可以在任何情况下打印每个字母(YES、yes、Yes 都将被识别为肯定答案,NO、no 和 nO 都将被识别为否定答案)。

示例

输入 #1

4
ababa
ba
ababa
bb
aaa
aaaa
aababa
ababa

输出 #1

YES
NO
NO
YES

注意

考虑语句中的示例测试。

为了从“ababa”获得“ba”,您可以按退格键而不是输入第一个和第四个字符。

输入“ababa”时无法获得“bb”。

输入“aaa”时无法获得“aaaa”。

为了在输入“aababa”时获得“ababa”,您必须按退格键而不是输入第一个字符,然后输入所有剩余的字符。