@[越学越掂](/user/38886)
题目要求确定最长且最先出现的匹配的括号子串,由于匹配的括号子串必定是左右对称的,实际上问题转化为在给定字符串中求最长回文子串(如果有多个同等长度的最长回文子串则取最先出现的一个),结合题目的数据约束,使用Manacher算法最为合适(如果您对Manacher算法不够熟悉,可以参考网上的博客文章或者我写的书[《C++,挑战编程——程序设计竞赛进阶训练指南》](https://blog.csdn.net/metaphysis/article/details/90288252)第11章第11.10.6“最长回文子串”一节的内容)。
对于您的代码,以下是Hack数据:
```
(]]]()[])))[][]
```
您的输出:
```
()[])
```
by metaphysis @ 2020-09-07 20:38:19
```cpp
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define rep(i,a,b,k) for(register ll i=a;i<=b;i+=k)
#define drep(i,a,b,k) for(register ll i=a;i>=b;i-=k)
using namespace std;
const int mn=1e6+5;
stack<char> st;
string s;
int len=0,ans,now,ansi;
bool sus[mn];
int main()
{
cin>>s;
len=s.length();
rep(i,0,len-1,1)
{
if(s[i]=='('||s[i]=='[')
{
st.push(s[i]);
now=1;
}
else if((st.size())&&((s[i]==')'&&st.top()=='(')||(s[i]==']'&&st.top()=='[')))
{
sus[i]=1;
sus[i-now]=1;
st.pop();
now+=2;
if(st.empty())
now=1;
}
else
{
st.push(s[i]);
now++;
}
}
now=0;
rep(i,0,len-1,1)
{
if(!sus[i])
now=0;
else
{
now++;
if(now>ans)
{
ans=now;
ansi=i;
}
}
}
/*rep(i,0,len-1,1)
cout<<sus[i]<<' ';
cout<<ans<<' '<<ansi;*/
if(ans==1)
cout<<"\n";
else
rep(i,ansi-ans+1,ansi,1)
printf("%c",s[i]);
return 0;
}
```
md,为啥改了还错啊
by 越学越掂 @ 2020-09-12 21:40:22
([]())
by Myzc @ 2020-11-20 17:00:26