#P1944. 最长括号匹配

最长括号匹配

题目描述

对一个由 ()[] 四种括号组成的字符串,求出其中最长的括号匹配子串。具体来说,满足如下条件的字符串成为括号匹配的字符串:

  • ()[] 是括号匹配的字符串。

  • A 是括号匹配的串,则 (A)[A] 是括号匹配的字符串。

3.若 AB 都是括号匹配的字符串,则 AB 也是括号匹配的字符串。

例如:()[]([])()() 都是括号匹配的字符串,而 ][[(]) 则不是。

字符串 AA 的子串是指由 AA 中连续若干个字符组成的字符串。

例如,ABCABCCABABCABC 都是字符串 ABCABC 的子串,而 DBAACB 则不是。空串是任何字符串的子串。

输入格式

输入一行,为一个仅由 ()[] 组成的非空字符串。

输出格式

输出一行,为最长的括号匹配子串。若有相同长度的子串,输出在原字符串内出现位置靠前的子串。

([(][()]]()

[()]

())[]
()

提示

数据范围

nn 为输入字符串的长度。

对于 20%20\% 的数据,n102n \le {10}^2

对于 50%50\% 的数据,n104n \le {10}^4

对于 100%100\% 的数据,n106n \le {10}^6