CF思维联系–CodeForces -224C - Bracket Sequence
CF思维联系–CodeForces -224C - Bracket Sequence
ACM思维题训练集合 A bracket sequence is a string, containing only characters “(”, “)”, “[” and “]”.
A correct bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters “1” and “+” between the original characters of the sequence. For example, bracket sequences “()[]”, “([])” are correct (the resulting expressions are: “(1)+[1]”, “([1+1]+1)”), and “](” and “[” are not. The empty string is a correct bracket sequence by definition.
A substring s[l… r] (1 ≤ l ≤ r ≤ |s|) of string s = s1s2… s|s| (where |s| is the length of string s) is the string slsl + 1… sr. The empty string is a substring of any string by definition.
You are given a bracket sequence, not necessarily correct. Find its substring which is a correct bracket sequence and contains as many opening square brackets «[» as possible.
Input The first and the only line contains the bracket sequence as a string, consisting only of characters “(”, “)”, “[” and “]”. It is guaranteed that the string is non-empty and its length doesn’t exceed 105 characters.
Output In the first line print a single integer — the number of brackets «[» in the required bracket sequence. In the second line print the optimal sequence. If there are more than one optimal solutions print any of them. Examples
Input ([]) Output 1 ([]) Input ((( Output 0 括号是就近匹配的，所以可以用栈来模拟，所以可以将括号压栈，匹配后出栈，最后栈底剩余的就是不能出栈的就是不能匹配的，一般的方法是找到这些括号但是太费劲了，我们同时建立一个栈，同时入栈，出栈，存括号的下标，那么在出栈操作之后，第一个stack就只剩下不匹配的括号，第二个stack就只剩下不匹配的括号的下标。 下标将括号数组分成了好几段，枚举每一段的左中括号的数量即可，比较最大值更新左右段点即可
#include <bits/stdc++.h>
using namespace std;
template <typename t>
void read(t &x)
{
char ch = getchar();
x = 0;
int f = 1;
while (ch < '0' || ch > '9')
f = (ch == '-' ? -1 : f), ch = getchar();
while (ch >= '0' && ch <= '9')
x = x * 10 + ch - '0', ch = getchar();
x *f;
}
#define wi(n) printf("%d ", n)
#define wl(n) printf("%lld ", n)
#define P puts(" ")
typedef long long ll;
#define MOD 1000000007
#define mp(a, b) make_pair(a, b)
//---------------https://lunatic.blog.csdn.net/-------------------//
const int N = 1e5 + 5;
char a[N];
stack<char> m;
stack<int> n;
vector<int> x;
int main()
{
scanf("%s", a);
int ln = strlen(a);
int cnt = 0;
//cout<<ln<<endl;
for (int i = 0; i < ln; i++)
{
if (!m.size() || a[i] == '(' || a[i] == '[')
{
m.push(a[i]);
n.push(i);
continue;
}
else if (a[i] == ')' && m.top() == '(')
{
n.pop();
m.pop();
//cout << 1 << endl;
}
else if (a[i] == ']' && m.top() == '[')
{
m.pop();
n.pop();
cnt++;
// cout << 2 << endl;
}
else
{
m.push(a[i]);
n.push(i);
}
}
// cout<<1<<endl;
if (m.empty())
{
wi(cnt);
P;
printf("%s\n", a);
}
else
{
x.push_back(ln);
while (!n.empty())
{
x.push_back(n.top());
n.pop();
}
x.push_back(-1);
int ml, mr, maxi = 0;
cnt = 0;
for (int i = x.size() - 1; i > 0; i--)
{
maxi = 0;
// cout << x[i] + 1 << " " << x[i - 1] - 1 << endl;
for (int j = x[i] + 1; j < x[i - 1]; j++)
{
if (a[j] == '[')
maxi++;
}
if (maxi > cnt)
{
cnt = maxi;
ml = x[i] + 1;
mr = x[i - 1] - 1;
}
}
wi(cnt);
P;
if (cnt == 0)
return 0;
for (int i = ml; i <= mr; i++)
{
putchar(a[i]);
}
P;
}
//P;
}