← 返回题目列表

Codeforces · 1272/F

F. 两个括号序列

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

给定两个括号序列(不一定是常规的)$$$s$$$ 和 $$$t$$$,仅由字符“(”和“)”组成。您想要构造最短的常规括号序列,其中包含两个给定的括号序列作为子序列(不一定是连续的)。

回想一下什么是常规括号序列:

- () 是常规括号序列;
- 如果 $$$S$$$ 是常规括号序列,则 ($$$S$$$) 是常规括号序列;
- 如果 $$$S$$$ 和 $$$T$$$ 为常规括号序列,则 $$$ST$$$ ($$$S$$$ 和 $$$T$$$ 的串联)是常规括号序列。

回想一下,字符串 $$$s$$$ 的子序列是这样的字符串 $$$t$$$,可以通过删除一些(可能是零)字符从 $$$s$$$ 获得。例如,“coder”、“force”、“cf”和“cores”是“codeforces”的子序列,但“fed”和“z”不是。

输入

输入的第一行包含一个括号序列 $$$s$$$,由不超过 $$$200$$$ 字符“(”和“)”组成。

输入的第二行包含一个括号序列 $$$t$$$,由不超过 $$$200$$$ 字符“(”和“)”组成。

输出

打印一行 — 最短的常规括号序列,其中包含两个给定的括号序列作为子序列(不一定是连续的)。如果有多个答案,您可以打印任何一个。

示例

输入 #1

(())(()
()))()

输出 #1

(())()()

输入 #2

)
((

输出 #2

(())

输入 #3

)
)))

输出 #3

((()))

输入#4

())
(()(()(()(

输出#4

(()()()(()()))