对一个由(,),[,]括号组成的字符串，求出其中最长的括号匹配子串。具体来说，满足如下条件的字符串成为括号匹配的字符串：
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.
栈思想的一道好题啊！
直接把左括号压进栈里，如果能匹配，就都弹栈，然后用b[i]=1表示第i位是否成功匹配。
然后在b数组中最长的一段b[i]=1的直接输出就好了。
#include <stdio.h> #include <iostream> #include <string.h> #include <string> using namespace std; string s1; int s2,cnt,l1,top,stack[1000001][2],len,b[1000001]; signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); register int i,j(0),k(0); getline(cin,s1);//读一整行字符串 len=s1.length();//字符串长度 for(i=0;i<len;i++) { if((stack[top][0]=='[' && s1[i]==']') || (stack[top][0]=='(' && s1[i]==')'))//检查在栈里的元素和字符串的元素括号是否匹配 { b[stack[top--][1]]=b[i]=1;//如果匹配就弹栈 } else//不匹配 { stack[++top][0]=s1[i];//进入栈 stack[top][1]=i; } } for(i=0;i<len;i++)//开始遍历b数组 { if(b[i]==0)//如果遇到无法匹配的了，就清0，从头再来数可能最长的。 { cnt=0; l1=i+1; } else { cnt++;//计数 if(cnt>s2)//如果答案比已知最佳答案还要最优 { s2=cnt;//取最优答案 j=l1;//j是这段答案的左区间 k=i;//k是右区间 } } } for(i=j;i<=k;i++) { cout<<s1[i]; } cout<<endl; return 0; }
