p1944最长括号匹配

题目描述

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

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

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

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

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

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

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

输入格式

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

输出格式

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

输入输出样例

输入 #1

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

输出 #1

1
[()]

输入 #2

1
())[]

输出 #2

1
()

d[ i ] 表示以 i 结尾的最长括号序列。

‘ [ ’ , ‘ ( ‘ 结尾的长度肯定为 0

$d[ i ] = d[ i-1 ] + 2 + d[ i - d[ i-1] -2]$ ;

（题解区大佬的）：用栈记录匹配的下标 （ vis[ i ] = 1） , 然后计算最长的 ‘1’ 串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const int MAX=1000000+10;
char a[MAX];
int l,d[MAX],f,e,_max;
int main(){
	freopen("in","r",stdin);
	scanf("%s",a);
	l=strlen(a);
	fi(i,1,l){
		if((a[i]==')' && a[i-d[i-1]-1]=='(') || (a[i]==']' && a[i-d[i-1]-1]=='['))
			d[i]=d[i-1]+ 2 + d[i-d[i-1]-2];
		if(_max<d[i]){
			_max=d[i];
			e=i+1;f=i-d[i]+1;
		}
	}
	fi(i,f,e)
		putchar(a[i]);
	return 0;
}