Longest Bracket Matching

Problem Statement

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

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

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

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

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

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

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

Input

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

Output

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

Sample #1

Sample Input #1

1

([(][()]]()

Sample Output #1

1

[()]

Sample #2

Sample Input#2

1

())[]

Sample Output #2

1

()

Contraints

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

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

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

Solving

考虑使用动态规划解决此问题：

对于此类括号匹配问题，同线性动态规划的思想一样

我们定义dp[i]为以第i个括号结尾能向左延申获得的最大合法括号子序列的长度

所以我们首先能得到如果第i个括号是左括号（’(’ or ‘[’）的情况下，其不可能再向左延申，故其值为0：

$$ dp[i] = 0 \space\space\space\space\space\space\space[\text{s[i]=='(' or '['}] $$

重点是当第i个括号为右括号（’)’ or ‘]’）时:

此时我们优先查看dp[i-1]代表的最长子序列长度，在其序列的最左端的边界(left-1)是否是一个左括号(要一一配对，不可(]相配)，如果有则需要在dp[i-1]的基础上＋2，并且也要再加上那个左括号左边那一个序号代表的最长子序列长度(dp[i-1-dp[i-1]-2])

此时总的状态转移方程为：

$$ if[\text{s[i]=='(' or '['}]\\then\\dp[i] = 0 \\ if[\text{(s[i]==')' and s[i-1-dp[i-1]=='(')or(s[i]==']' and s[i-1-dp[i-1]=='[')}]\\then \\dp[i] = dp[i-1] + 2 - dp[i-2-dp[i-1]] $$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55


#include <bits/stdc++.h>
//#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f
#define NINF -0x3f3f3f3f
#define Single
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N = 1e6+10;
const int M = 0; 
int dp[N];
void solve()
{
    string s;
    cin >> s;
    int n = s.size();
    s = "#" + s;
    int ans = 0;
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='('||s[i]=='[') continue;
        if(s[i]==')'||s[i]==']')
        {
            if((s[i]==')' and s[i-1-dp[i-1]]=='(')or(s[i]==']' and s[i-1-dp[i-1]]=='['))
            {
                dp[i] = dp[i-1] + 2 + dp[i-2-dp[i-1]];
                ans = max(ans,dp[i]);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(ans==dp[i])
        {
            cout << s.substr(1+i-ans,ans);
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int T;
#ifdef Single
    T = 1;
#else
    cin >> T;
#endif
    while(T--)
    {
        solve();
    }
    return 0;
}