最长括号匹配 (线性DP)

最长括号匹配

题目描述

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

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

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

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

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

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

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

([(][()]]()

样例输出 #1

[()]

样例 #2

样例输入 #2

())[]

样例输出 #2

()

提示

【数据范围】

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

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

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

身败名裂，想了一个栈模拟，全WA。

没有考虑到
([]())

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 和 c 匹配了
                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;
    }

}

非常巧妙的一道题。

可能下次做又忘了做法了

考虑 $f[i-1]$ 的含义即可

/*
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;
}