最长括号匹配_NOI导刊2009提高（1）

发表于

原题地址

题目描述

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

1.(),[]是括号匹配的字符串。

2.若A是括号匹配的串，则(A),[A]是括号匹配的字符串。

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

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

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

例如，A,B,C,ABC,CAB,ABCABC都是ABCABC的子串。空串是任何字符串的子串。

输入输出格式

输入格式：

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

输出格式：

输出也仅有一行，为最长的括号匹配子串。若有相同长度的子串，输出位置靠前的子串。

输入输出样例

输入样例#1：

1
([(][()]]()

输出样例#1：

1
[()]

输入样例#2：

1
())[]

输出样例#2：

1
()

说明

【数据范围】

对20%的数据，字符串长度<=100.

对50%的数据，字符串长度<=10000.

对100%的数据，字符串长度<=1000000.

题解

转移方程不太好想

令f[i]表示以i为右端点最多能向左扩展的距离

具体见代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char s[1000001];
int F[1000001],len,ans;
int main(){
	scanf("%s",&s);
	len=strlen(s);
	for(int i=0;i<len;++i){
		if(s[i]=='('||s[i]=='[]')continue;
		else{
			if((s[i]==')'&&s[i-1-F[i-1]]=='(')||(s[i]==']'&&s[i-1-F[i-1]]=='['))
			F[i]=F[i-1]+2+F[i-2-F[i-1]];
		}
	}
	for(int i=0;i<len;++i)
	ans=max(ans,F[i]);
	for(int i=0;i<len;++i){
		if(F[i]==ans){
			for(int j=i-ans+1;j<=i;++j)
			printf("%c",s[j]);
			break;
		}
	}
}