元旦联欢会上,老师为信息学社团的同学举办了构造大赛,由老师给出两个括号序列,看谁能最快构造出最短的满足要求的括号序列,具体规则如下:对于两个字符串 、,若字符串 是 的一个子序列(不要求连续),则称 包含了 。
给出两个只由 ( 和 ) 组成的括号串 、。你需要构造一个字符串 ,要求同时满足:
- 字符串 包含 ;
- 字符串 包含 ;
- 是一个合法括号串。
构造大赛要求学生写出一种 的具体方案,但为了方便,你只需要求出满足上述条件的字符串 的最短长度即可。
其中,合法括号串定义如下:
() 是合法括号串;
- 若 是合法括号串,则 也是合法括号串;
- 若 和 都是合法括号串,则 也是合法括号串。