The longest bracket matches

Title Description

For one by (,),[,] A string of parentheses , Find the longest bracket matching substring . say concretely , A string that meets the following conditions becomes a string that matches parentheses ：

1.(),[] Is a string matching parentheses .

2. if A Is a string matching parentheses , be (A),[A] Is a string matching parentheses .

3. if A,B Is a string matching parentheses , be AB It is also a string matching parentheses .

for example ：(),[],([]),()() Are strings that match parentheses , and ][,[(]) It is not .

character string A The substring of is defined by A A string of consecutive characters in .

for example ,A,B,C,ABC,CAB,ABCABCd All are ABCABC The string of . An empty string is a substring of any string .

Input format

The input line , Is a ()[] A non empty string composed of .

Output format

There is only one line of output , Match substrings for the longest parentheses . If there are substrings of the same length , The substring with the front output position .

Examples #1

The sample input #1

([(][()]]()

Sample output #1

[()]

Examples #2

The sample input #2

())[]

Sample output #2

()

Tips

【 Data range 】

Yes 20% The data of , String length <=100.

Yes 50% The data of , String length <=10000.

Yes 100% The data of , String length <=1000000.

reputation , Think of a stack simulation , whole WA.

 Not considered 
([]())

vector<char>tmp,res;
stack<char>stk,empty;
void solve(){
    
    string s;
    cin>>s;
    for(auto c:s){
    
        // debug(stk.size());
        if(c == '[' || c == '(' ){
    
            stk.push(c);
        }
        else{
    
            if(!stk.size()){
    
            	tmp.clear();
            	continue;	
            }
            auto top = stk.top();
            if((top == '(' && c == ']') || (top == '[' && c==')')){
    
                stk = empty;
                tmp.clear();
            }
            else{
     // top  and  c  Match the 
                stk.pop();
                tmp.pb(c);

                if(res.size()<tmp.size()){
    
                    res = tmp;
                }
            
            }
        }
    }
    reverse(all(res));
    for(auto c:res){
    
    	if(c == ']')
	    	cout<<'[';
    	else
    		cout<<'(';
    }
    reverse(all(res));
    for(auto c:res){
    
    	cout<<c;
    }

}

A very clever question .

Maybe I forget to do it next time

consider $f[i-1]$ The meaning of

/* A: 10min B: 20min C: 30min D: 40min */ 
#include <iostream>
#include <stack>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#define pb push_back 
#define all(x) (x).begin(),(x).end()
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){
    for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){
    j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){
    for(auto c:v)os<<c<<" ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>&v){
    for(auto c:v)os<<c.first<<" "<<c.second<<endl;return os;}
template<typename T>inline void rd(T &a) {
    
    char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {
    if (c == '-')f = -1; c = getchar();}
    while (isdigit(c)) {
    x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}

typedef pair<int,int>PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=1e6+10;
int n,m,_;
int f[N];
void solve(){
    
    string s;
    cin>>s;
    n = s.size();
    s = " " + s;
    int ans = 0;
    for(int i=1;i<=n;i++){
    
        char c = s[i];
        if(c == ']' || c == ')' ){
    
            int l = i - f[i-1] - 1;
            if((c == ']' && s[l] == '[') || (c == ')' && s[l] == '(')){
    
                f[i] = f[i-f[i-1]] + 2;
            }
        }
        ans = max(ans,f[i]);
    }
    cout<<ans<<endl;
}

int main(){
    
	solve();
	return 0;
}