学步园

题意：给出一个包含[]()4种字符的一个字符串，长度不超过10^5，问正确的子串中最多含多少个“[”，并输出其中一个这样的字符串。

题目链接：http://codeforces.com/problemset/problem/223/A

——>>从左往右扫描，如果扫到"]"或者")"，判断其与栈顶字符是否匹配，如果出现错误匹配，那么说明栈顶字符到当前位置之间的子串表达式是不正确的，于是从下一位置开始重新扫描，最后求每一段正确表达式中的"["最大值。（注意正确表达式之间的连接）

#include <cstdio>

using namespace std;

const int maxn = 100000 + 10;

char s[maxn];
int cnt[maxn], st[maxn], p, Max, ret_L, ret_R, start;

void update(int L, int R) {
    if(cnt[R] - cnt[L-1] > Max) {
        Max = cnt[R] - cnt[L-1];
        ret_L = L;
        ret_R = R;
    }
}

int main()
{
    while(scanf("%s", s+1) == 1) {
        Max = 0;
        p = 0;
        start = 1;        //设置每一段的起始位
        cnt[0] = 0;
        for(int i = 1; s[i]; i++) {
            cnt[i] = cnt[i-1] + (s[i] == '[');
            if(s[i] == '[' || s[i] == '(') st[p++] = i;
            else if(p && ((s[i] == ']' && s[st[p-1]] == '[') || (s[i] == ')' && s[st[p-1]] == '('))) {
                p--;
                if(p > 0) update(st[p-1]+1, i);     //栈非空
                else update(start, i);      //栈空
            }
            else {
                p = 0;      //栈置空
                start = i+1;        //更新段起始位
            }
        }
        printf("%d\n", Max);
        if(Max) for(int i = ret_L; i <= ret_R; i++) putchar(s[i]);
        puts("");
    }
    return 0;
}