本文主要是介绍CF - 223 - A. Bracket Sequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给出一个包含[]()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;
}
这篇关于CF - 223 - A. Bracket Sequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
