最长合法括号子串

题意

一个合法的括号字符串满足以下条件：

1. 字符串“()”被认为是合法的。
2. 如果字符串 “X” 与 “Y” 是合法的，则 “XY” 也被认为是合法的。
3. 如果字符串 “X” 是合法的，则 “(X)” 也是合法的。

例如，“()”，“()()”，“(())” 这些都是合法的。

现在，给定一个由 ( 和 ) 组成的字符串 SS。

请你求出其中的最长合法括号子串的长度以及数量。

输入格式

共一行，一个由 ( 和 ) 组成的字符串。

输出格式

一行两个整数，表示最长合法括号子串的长度以及数量。

如果不存在合法括号子串，则输出 0 1。

数据范围

前六个测试点满足：1≤|S|≤1001≤|S|≤100。 所有测试点满足：1≤|S|≤1061≤|S|≤106。

输入样例1：

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

输出样例1：

6 2

输入样例2：

))(

输出样例2：

0 1

思路

首先，对于每一个右括号，只有唯一的左括号与它对应。思路就是对于每一个右括号，向左找到最远的能够与它配对的括号，记录一下长度，然后在所有的长度里面找到最大的那个就是答案。

如何找到最靠左的配对的括号？我们使用一个栈就可以搞定了，在出入栈的过程中，合法的括号序列一定会被删除掉，也就是消去了，所以栈顶元素就是最远的。

代码

//最长合法括号子串
#include<iostream>
#include<stack>

using namespace std;

string str;
stack<int> stk;

int main()
{
    cin >> str;
    
    int resl = 0, resc = 1;
    for(int i = 0; i < str.size(); i++)
    {
        char c = str[i];
        if(c == '(') stk.push(i);
        else if(stk.size() && str[stk.top()] == '(') stk.pop();
        else stk.push(i);//注意，这里进栈的是下标
        
        int r;
        if(stk.size()) r = i - stk.top();
        else r = i + 1;
        
        if(r > resl) resl = r, resc = 1;
        else if(r == resl && r > 0) resc++;
    }
    
    cout << resl << " " << resc << endl;
    return 0;
}