← 返回题目列表

AtCoder · abc454_d

D. 括号叉叉

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

分数: 425 点

问题陈述

给你一个字符串 A 组成 (, x, ).
您可以对以下两种类型的操作 A 以任意顺序任意次数。

  • 选择子字符串的一次出现 (xx) in A 并将其替换为 xx.
  • 选择子字符串的一次出现 xx in 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 is xxx.
  • 更换 xx 来自 2nd 通过 3rd 字符 A 与 (xx)。经过这次操作后, A is x(xx).