分数: 425 点
问题陈述
给你一个字符串 A 组成 (, x, ).
您可以对以下两种类型的操作 A 以任意顺序任意次数。
- 选择子字符串的一次出现
(xx)in A 并将其替换为xx. - 选择子字符串的一次出现
xxin A 并将其替换为(xx).
给你一个字符串 B 组成 (, x, )。确定是否可以制作 A 等于 B.
你被给予 T 测试用例;解决它们中的每一个。
什么是子串
A 子字符串 长度为 $$$l$$$ 的字符串 $$$s_1s_2 \ldots s_l$$$ 的 of S 是从开头删除零个或多个字符,从结尾删除零个或多个字符得到的字符串 S.例如,
ab 是一个子串 abc,但是 ac 不是以下的子串 abc.
约束
- 1 \leq T \leq 3 \times 10^5
- A 和 B 是长度介于 1 和 2\times 10^6,包含在内,由以下组成
(,x,). - 总和 |A| + |B| 所有测试用例最多 2 \times 10^6 (其中 |A| 表示长度 A).
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出:
A B
输出
输出 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。
对于每个测试用例,输出 Yes 如果你可以 A 等于 B,和 No 否则。
示例输入 1
6 (xx)x x(xx) (x)x (xx) )x()x( )x()x( x (x) (((((xx)))))x x((((((((((xx)))))))))) ((xx)xx)xx (x((xx))x)(xx)
示例输出 1
Yes No Yes No Yes Yes
例如,在第一个测试用例中,您可以使 A 等于 B 通过以下程序:
- 更换
(xx)来自 1st 通过 4个字符 A 与xx。经过这次操作后, A isxxx. - 更换
xx来自 2nd 通过 3rd 字符 A 与(xx)。经过这次操作后, A isx(xx).