CF思维联系–CodeForces -224C

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;

}

巴特西

CF思维联系–CodeForces -224C - Bracket Sequence

最新文章

热门文章