题目地址：Codeforces：Problem – 5C – Codeforces、洛谷：CF5C Longest Regular Bracket Sequence – 洛谷 | 计算机科学教育新生态

题目描述

This is yet another problem dealing with regular bracket sequences.

We should remind you that a bracket sequence is called regular, if by inserting «+» and «1» into it we can get a correct mathematical expression. For example, sequences «(())()», «()» and «(()(()))» are regular, while «)(», «(()» and «(()))(» are not.

You are given a string of «(» and «)» characters. You are to find its longest substring that is a regular bracket sequence. You are to find the number of such substrings as well.

题意简述

给一个括号序列，求其最长的完全匹配连续子串长度及数量。

输入输出格式

输入格式：
The first line of the input file contains a non-empty string, consisting of «(» and «)» characters. Its length does not exceed 10^6.

输出格式：
Print the length of the longest substring that is a regular bracket sequence, and the number of such substrings. If there are no such substrings, write the only line containing “0 1”.

输入输出样例

输入样例#1：

)((())))(()())

输出样例#1：

6 2

输入样例#2：

))(

输出样例#2：

0 1 

题解

求括号序列匹配的常用方式是利用栈，即遇到一个左括号将其放入栈中，遇到一个右括号取栈顶元素并将这一对括号设置为已匹配。如果中间出现了未匹配段，则一定是右括号有多的，因此连续的已匹配段构成的子串一定是完全匹配子串。计算出匹配情况后，统计连续匹配的最长段及其数量即可。

代码

// Code by KSkun, 2019/6
#include <cstdio>
#include <cstring>

#include <algorithm>
#include <stack>

const int MAXN = 1000005;

int n;
bool match[MAXN];
char s[MAXN];
std::stack<int> sta;

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for(int i = 1; i <= n; i++) {
        if(s[i] == '(') sta.push(i);
        else {
            if(sta.empty()) continue;
            int l = sta.top(); sta.pop();
            match[l] = match[i] = true;
        }
    }
    int mx = 0, mxcnt = 1, now = 0;
    for(int i = 1; i <= n; i++) {
        if(match[i]) {
            now++;
        } else {
            if(now > mx) {
                mx = now; mxcnt = 1;
            } else if(now == mx) {
                mxcnt++;
            }
            now = 0;
        }
    }
    if(now > mx) {
        mx = now; mxcnt = 1;
    } else if(now == mx) {
        mxcnt++;
    }
    if(mx == 0) mxcnt = 1;
    printf("%d %d", mx, mxcnt);
    return 0;
}