$PS$

• 欢迎在评论区谔谔，$dalao$发现博文有误麻烦在评论区斧正，弱弱感激不尽
• 萌新初学$OI$(骗管理员神仙的)，求管理员通过
• 蒟蒻写博文不易，请不要直接$Ctrl+S→Ctrl+V$

对于这题$\le 1000000$的数据规模显然只允许我们用一重循环

最长，可见这是道最值问题

最值问题可以用贪心，$DP$，二分，$etc$

我对于这题用的是$DP$太弱了，只会DP

进入正题：如何$DP$

首先，我们需要构建状态，状态的构建不是唯一的，受最长上升子序列（好题废话）的影响，我是这样构建的

令$f[i]$表示以$s[i]$为结尾的字符串的最长括号匹配

接下来，我们就得推状态转移方程

考虑$s[i]$，要想它能构成括号匹配，很显然地，它肯定不能为(或者[

那么$s[i]$为)或者]时我们应该怎样转移呢？

我们要找到一个$s[k]=$((或者[，为了方便叙述，下同)，使得在$(k,i)$这个开区间内的字符串为最长括号匹配且$[k,i]$这个闭区间尽可能得大

那么什么情况能满足上面的条件呢？

$f[i-1]$表示什么？不正是以$s[i-1]$结尾的最长括号匹配吗，那么如果$s[i-1-f[i-1]]$与$s[i]$匹配的话，$f[i]$一定等于$f[i-1]+2+f[i-f[i-1]-2]$

说明一下

• $f[i-1]$代表$s[i-1-f[i-1]]$与$s[i]$中间的一段即$s[i-1]$的最长括号匹配
• $2$即$s[i-1-f[i-1]]$与$s[i]$匹配，增加长度为$2$
• $s[i-f[i-1]-2]$即$s[i-f[i-1]-1]$的前一个字符，这里不要漏掉它还可以构成的最长括号匹配的长度
• 不是很复杂，画个图就很明显了

那么若$s[i-1-f[i-1]]$与$s[i]$不匹配怎么办？这时$f[i]$肯定为$0$，因为除此之外，不管选哪个字符，都没法满足它和$s[i]$构成括号匹配

分析千万条，代码第一条，不懂的看一下代码(懂得可以自己打去了，偷笑)

$my~Code$

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;

const int L=1000005;
char s[L];
int l,f[L],Ans,id;

int main()
{
	scanf("%s",s+1);//输入，下标从1开始
	l=strlen(s+1);//下标从1开始的字符串长度
	for(int i=2;i<=l;++i)//s[1]显然无法匹配，所以从2开始
		if(s[i]=='('||s[i]=='[') continue;//如分析
		else
			if((s[i]==')'&&s[i-f[i-1]-1]=='(')
			||(s[i]==']'&&s[i-f[i-1]-1]=='['))
			{
				f[i]=f[i-1]+2+f[i-f[i-1]-2];
				if(f[i]>Ans) Ans=f[i],id=i;//Ans记录最长括号匹配，id记录最长括号匹配的下标
			}
	for(int i=id-Ans+1;i<=id;++i) printf("%c",s[i]);
	putchar('\n');
	return 0;
}

#include <bits/stdc++.h> 
using namespace std; 
#define int long long 
#define INF 0x3f3f3f3f3f3f3f3f 
#define N (int)(1e6+15)
int n, ans, dp[N], id; 
char s[N]; 
signed main() { 
    scanf("%s", (s+1));
    n = strlen(s+1); 
    for(int i = 2; i <= n; i++) { 
        if(s[i] == '(' || s[i] == '[') continue; 
        else { 
            if((s[i] == ')' && s[i-dp[i-1]-1] == '(') || 
               (s[i] == ']' && s[i-dp[i-1]-1] == '[')) { 
                dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]; 
                if(dp[i] > ans) {
                    ans = dp[i];
                    id = i; 
                }
            } 
        } 
    } 
    for(int i = id-ans+1; i <= id; i++) {
        putchar(s[i]); 
    }
    puts(""); 
    return 0; 
}

#include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(1e6+15) int n,ans,dp[N],id; char s[N]; signed main() { scanf("%s",(s+1));n=strlen(s+1); for(int i=2; i<=n; i++) { if(s[i]'('||s[i]'[')continue; else { if(s[i]')'&&s[i-dp[i-1]-1]'('|| s[i]']'&&s[i-dp[i-1]-1]'[') { dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2]; if(dp[i]>ans)ans=dp[i],id=i; } } } for(int i=id-ans+1; i<=id; i++) putchar(s[i]); puts(""); return 0; }