原题链接
考察:栈,模拟
??模拟栈匹配,不匹配的留入栈里.然后栈里都是不匹配的坐标,相邻之间都是匹配的.
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
char s[N],res[N];
int match[N],top,stk[N],sum[N];
int main()
{
scanf("%s",s+1);
int len = strlen(s+1);
//这样栈存储的都是不配对的下标,这之间都是配对的.
for(int i=1;i<=len;i++)
{
if(s[i]==‘[‘) sum[i]++;
sum[i] += sum[i-1];
}
for(int i=1;i<=len;i++)
{
if(!top) stk[++top] = i;
else if(s[stk[top]]==‘(‘&&s[i]==‘)‘) top--;
else if(s[stk[top]]==‘[‘&&s[i]==‘]‘) top--;
else stk[++top] = i;
}
stk[++top] = len+1;
int ans = -1,ansl,ansr;
for(int i=1;i<=top;i++)
{
int l = stk[i-1],r = stk[i]-1;
if(sum[r]-sum[l]>ans)
{
ans = sum[r]-sum[l];
ansl = l+1,ansr = r;
}
}
printf("%d\n",ans);
for(int i=ansl;i<=ansr;i++)
res[i-ansl] = s[i];
res[ansr+1] = ‘/0‘;
printf("%s\n",res);
return 0;
}