对一个由(,),[,]括号组成的字符串,求出其中最长的括号匹配子串。具体来说,满足如下条件的字符串成为括号匹配的字符串:
1.(),[]是括号匹配的字符串。
2.若A是括号匹配的串,则(A),[A]是括号匹配的字符串。
3.若A,B是括号匹配的字符串,则AB也是括号匹配的字符串。
例如:(),[],([]),()()都是括号匹配的字符串,而][,[(])则不是。
字符串A的子串是指由A中连续若干个字符组成的字符串。
例如,A,B,C,ABC,CAB,ABCABC都是ABCABC的子串。空串是任何字符串的子串。输入一行,为一个仅由()[]组成的非空字符串。
输出也仅有一行,为最长的括号匹配子串。若有相同长度的子串,输出位置靠前的子串。
([(][()]]()
[()]
())[]
()
【数据范围】
对20%的数据,字符串长度<=100。
对50%的数据,字符串长度<=10000。
对100%的数据,字符串长度<=1000000。