当前位置:首页 > 数据结构 > > 正文
洛谷P1944最长括号匹配[NOI导刊]
154+

题目大意:一个括号序列,请问最长的匹配序列是什么?若有多个最长的,输出位置靠前的。

题目描述

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

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]就是合法的。

最后就是细节问题,不合法的时候,没有对应左括号,无左端点;记录合并后的序列后,打擂台记录最大值的位置。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,

洛谷P1944最长括号匹配[NOI导刊]:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter