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<sup class="upper-index">6</sup>.
#include <cstdio>
#include <vector>
#include <cstring>
 
using namespace std;
 
int dp[1234567];
char s[1234567];
 
int main() {
    gets(s);
    int n = strlen(s);
    vector<int> st;
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n; i++) {
        if (s[i] == '(') {
            st.push_back(i);
        }
        else {
            if (st.empty()) {
            }
            else {
                int he = st[st.size() - 1];
                st.pop_back();
                if (!he) dp[i] = i + 1;
                else dp[i] = dp[he - 1] + i - he + 1;
            }
        }       
    }   
    int ans = 0, cnt = 1;
    for (int i = 0; i < n; i++) {
        if (dp[i] == ans) {
            cnt++;
        }
        else if (dp[i] > ans) {
            ans = dp[i];
            cnt = 1;
        }
    }
    if (!ans) cnt = 1;
    printf("%d %d\n", ans, cnt);
    return 0;
}