洛谷P1944最长括号匹配[NOI导刊]
820+
作者：crxis 发布：2021-06-23 分类：栈
题目大意：一个括号序列，请问最长的匹配序列是什么？若有多个最长的，输出位置靠前的。
题目描述
对一个由(,),[,]括号组成的字符串，求出其中最长的括号匹配子串。具体来说，满足如下条件的字符串成为括号匹配的字符串：
1.(),[]是括号匹配的字符串。
2.若A是括号匹配的串，则(A),[A]是括号匹配的字符串。
3.若A,B是括号匹配的字符串，则AB也是括号匹配的字符串。
例如：(),[],([]),()()都是括号匹配的字符串，而][,[(])则不是。
字符串A的子串是指由A中连续若干个字符组成的字符串。
例如，A,B,C,ABC,CAB,ABCABCd都是ABCABC的子串。空串是任何字符串的子串。
输入输出格式
输入格式
输入一行，为一个仅由()[]组成的非空字符串。
输出格式
输出也仅有一行，为最长的括号匹配子串。若有相同长度的子串，输出位置靠前的子串。
输入输出样例
输入样例 #1
([(][()()
输出样例 #1
[()]
输入样例 #2
())[]输出样例 #2
()说明
【数据范围】
对20%的数据，字符串长度<=100.
对50%的数据，字符串长度<=10000.
对100%的数据，字符串长度<=1000000.
解题思路
首先，用栈预处理出每个右括号r对应的左括号位置l，序列[l, r]就是合法的；
然后，处理多个合法序列，如[x, y]和[l, r]都是合法的，且相邻，那么[x, r]就是合法的。
最后就是细节问题，不合法的时候，没有对应左括号，无左端点；记录合并后的序列后，打擂台记录最大值的位置。
程序实现
