#P1944. 最长括号匹配
最长括号匹配
题目描述
对一个由 (
、)
、[
、]
四种括号组成的字符串,求出其中最长的括号匹配子串。具体来说,满足如下条件的字符串成为括号匹配的字符串:
-
()
、[]
是括号匹配的字符串。 -
若
A
是括号匹配的串,则(A)
、[A]
是括号匹配的字符串。
3.若 A
、B
都是括号匹配的字符串,则 AB
也是括号匹配的字符串。
例如:()
、[]
、([])
、()()
都是括号匹配的字符串,而 ][
、[(])
则不是。
字符串 的子串是指由 中连续若干个字符组成的字符串。
例如,A
、B
、C
、ABC
、CAB
、ABCABC
都是字符串 ABCABC
的子串,而 D
、BA
、ACB
则不是。空串是任何字符串的子串。
输入格式
输入一行,为一个仅由 ()[]
组成的非空字符串。
输出格式
输出一行,为最长的括号匹配子串。若有相同长度的子串,输出在原字符串内出现位置靠前的子串。
([(][()]]()
[()]
())[]
()
提示
数据范围
记 为输入字符串的长度。
对于 的数据,。
对于 的数据,。
对于 的数据,。