学步园

http://blog.csdn.net/acm_ted/article/details/8022419

第三题：Bracket Sequence

题意：给你一段只包含'(',')','[',']'的字符串，问哪段子串的括号匹配是正确的且包含尽可能多的'['。

题解：用num数组记录前i个字符包含'['的个数，再计算以第i个字符开始，符合条件的字符串的长度，用l数组记录，最后查找最优值。

代码：

#include<cstdio>
#include<cstring>
using namespace std;
#define M 100005
char s[M];
int num[M],l[M];
bool check(char a,char b)
{
    return ((a=='('&&b==')')||(a=='['&&b==']'));
}
int main()
{
    scanf("%s",s);
    int len=strlen(s);
    memset(l,0,sizeof(l));
    num[0]=0;
    for(int i=0; i<len; ++i)
        num[i+1]=num[i]+(s[i]=='[');
    for(int i=len-2; i>=0; --i)
    {
        if(s[i]==')'||s[i]==']') continue;
        int idx=i+1+l[i+1];
        if(check(s[i],s[idx]))
            l[i]=idx-i+1+l[idx+1];
    }
    int ans=0,st=0;
    for(int i=0; i<len; ++i)
        if(ans<num[i+l[i]]-num[i])
        {
            ans=num[i+l[i]]-num[i];
            st=i;
        }
    printf("%d\n",ans);
    for(int i=0; i<l[st]; ++i)
        printf("%c",s[st+i]);
    printf("\n");
    return 0;
}