题意描述

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

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

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

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

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

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

例如,A,B,C,ABC,CAB,ABCABC都是ABCABC的子串。

规定空串是任何字符串的子串。

现在问题来了,给你一个字符串,请求出它的最长匹配子串。


输入格式

输入包含一行,为一个仅由( , ) , [ , ]组成的非空字符串$s$。


输出格式

输出也仅有一行,为$s$的最长的括号匹配子串。

若有相同长度的子串,则请输出位置靠前的子串。


Input & Output ‘s examples

Input ‘s eg

([(][()]]()

Output ‘s eg

[()]

数据范围和约定

设$|s|$为字符串$s$的长度

对于$20\%$的数据,$1 \leq |s| \leq 100$。

对于$50\%$的数据,$1 \leq |s| \leq 10^4$。

对于$100\%$的数据,$1 \leq |s| \leq 10^6$。


分析

一道比较套路化的$\text{dp}$模型。

设$f[i]$表示以$s[i]$为结尾的最长匹配子串的长度,则每一个状态可以由其上一位转移而来。

之后考虑如何进行转移。

如果第$i$位为左括号,则不可能构成一个以$s[i]$为结尾的匹配串。此时$f[i] = 0$

如果第$i$位为右括号,则考虑寻找其左边第一个没有匹配的左括号。显然,这之间是不可能有单独的右括号存在的。

也就是说,我们只需要确认当前位置减去前一个位置的最长匹配长度,即$s[i - 1 - f[i - 1]]$是不是左括号即可。是的话,则

最后循环一遍,找到最大长度,之后输出子串。

时间复杂度为$O(n)$,足以通过$10^6$的数据。

剩下的见代码注释。


Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define ll long long
#define pb push_back
#define MP make_pair
#define ull unsigned long long
#define PII pair<int , int>
#define PIL pair<int , long long>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(a))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

using namespace std;

const int N = 10001;
const int M = 100001;
const int HA = 998244353;
const int INF = 2147483647;
const long long INFL = 9223372036854775807;

char s[10 * M];
int f[10 * M] , ans; //f[i] 以i为结尾的最长匹配子串长度

int main() {
#ifdef LOCAL
freopen("try.in" , "r" , stdin);
freopen("try1.out" , "w" , stdout);
#endif
scanf("%s" , s + 1); //将字符串统一右移一位以避免负下标
int len = strlen(s + 1);
rep(i , 1 , len){
if(s[i] == '(' || s[i] == '[') continue; //左括号则跳过
if(s[i] == ')' || s[i] == ']'){
if((s[i] == ')' && s[i - 1 - f[i - 1]] == '(') || (s[i] == ']' && s[i - 1 - f[i - 1]] == '[')){
f[i] = f[i - 1] + 2 + f[i - 2 - f[i - 1]];
//右括号的话则等于其上一位长度 + 2 + 之前可以连接的子串长度
ans = max(ans , f[i]);
}
}
}
rep(i , 1 , len){
if(f[i] == ans){
rep(j , i - ans + 1 , i){
printf("%c" , s[j]);
}
return 0;
}
}

return 0;
}

THE END