本文主要是介绍CF Bracket Sequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://codeforces.com/problemset/problem/223/A
题意：给定一个只含有’[‘ ']' '(' ')' 的字符串，它不一定是合法的，求出它的一个含有 '[' 最多的并合法的字串。
思路：相当于括号匹配的问题，多了判断'['的个数而已。
以 )（[ ] )( 为例，该字符串每个字符对应下标为0 ,1,2,3,4,5用hash数组记录与当前字符串匹配的那个字符的下标，所以hash[0] = -1,
hash[1] = 4, hash[2] = 3,hash[3] = 2,hash[4] = 1, hash[5] = -1,如果当前字符没有被匹配，则初始化为-1，这样hash值为-1的两个字符之间就是一个合法的子串，然后求出每个合法子串中‘[’的长度，同时记录对应合法子串的起点和终点，最后取最大值即可。
#include<stdio.h>
#include<string.h>
#include<stack>
#include<algorithm>
using namespace std;struct node
{char ch;int id;
};char s[100010],tmp[100010],res[100010];
int len;
int hash[100010],ans;
stack <struct node> st;void solve()
{memset(hash,-1,sizeof(hash));while(!st.empty())st.pop();for(int i = 0; i < len; i++){if(s[i] == '[' || s[i] == '('){st.push((struct node){s[i],i});}else if(s[i] == ']'){if(!st.empty()){struct node u = st.top();if(u.ch == '['){hash[u.id] = i;hash[i] = u.id;st.pop();}else st.push((struct node){s[i],i});}else st.push((struct node){s[i],i});}else if(s[i] == ')'){if(!st.empty()){struct node u = st.top();if(u.ch == '('){hash[u.id] = i;hash[i] = u.id;st.pop();}else st.push((struct node){s[i],i});}else st.push((struct node){s[i],i});}}int cnt = 0,ans = -1,flag = 0,x,y;int i,j;for(i = 0; i < len;){if(hash[i] != -1){flag = 1;cnt = 0;for(j = i; hash[j] != -1; j++){if(s[j] == '[')cnt++;}if(cnt > ans){ans = cnt;x = i;y = j;}i = j+1;}elsei++;}if(flag == 0)printf("0\n");else{printf("%d\n",ans);for(int i = x; i < y; i++)printf("%c",s[i]);printf("\n");}
}int main()
{while(~scanf("%s",s)){len = strlen(s);solve();}return 0;
}
这篇关于CF Bracket Sequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
