题解 P1944 【最长括号匹配_NOI导刊2009提高（1）】

杨柏涵 · 2019-03-24 23:48:25 · 题解

主要思路： ① 依次入站遇到可以匹配的一对，就把这一对符号的序号放入一个桶数组pail中，并将这一对括号从栈stack中删除。 ②然后对桶数组中的最长连续子串进行统计即可。

#include <bits/stdc++.h>
using namespace std;
string s;
string t="";
string k="";
int maxx=0;
int stack[1000100];
int pail[1000100];
int main(){
    memset(pail,0,sizeof(pail));
    cin>>s;
    int top=0;
    int i=0;
    while(i<s.size()){
        stack[++top]=i;
        if((s[stack[top]]==')'&&s[stack[top-1]]=='('||s[stack[top]]==']'&&s[stack[top-1]]=='[')&&top-1>0){
            pail[stack[top]]=1;
            pail[stack[top-1]]=1;
            top-=2;
        }
        i++;
    }
    int ans=0;
    for(int i=0;i<s.size();i++){ 
        if(pail[i]){
            ans++;
            k+=s[i];
        }
        else{
            if(ans>maxx){
                maxx=ans;
                t=k;

            }
            k="";
            ans=0;
        }
    }
    cout<<t<<endl;
    return 0;
}