codeforce 5C 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.

Input
The first line of the input file contains a non-empty string, consisting of «(» and «)» characters. Its length does not exceed 106.

Output
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”.

Examples
input
)((())))(()())
output
6 2
input
))(
output
0 1

题意

给出一个括号序列，求出最长合法子串和它的数量。

题解

一般涉及到括号序列都用栈来模拟。

确立状态。$f[i]$表示i这个右括号最早合法的左括号匹配。

我们遇到左括号压到栈里，遇到右括号弹出。

弹出时统计一下$temp=stack.top()$。看一下$f[temp-1]$是否存在，存在则$f[i]=f[temp-1]$否则$f[i]=temp$

#include <cstdio>
#include <cstring>
#include <stack>
#define N 1000010
using namespace std;
char s[N];
stack<int>st;
int ans,cnt=1,f[N];
main()
{
    scanf("%s",s+1);
    int len=strlen(s+1);
    memset(f,-1,sizeof f);
    for (int i=1;i<=len;i++)
        if (s[i]=='(')
            st.push(i);
        else if (!st.empty())
        {
            f[i]=st.top();st.pop();
            int temp=f[i];
            if (f[temp-1]!=-1)
                f[i]=f[temp-1];
            if (i-f[i]+1>ans)
                ans=i-f[i]+1,cnt=1;
            else if (i-f[i]+1==ans)
                cnt++;
        }
    printf("%d %d",ans,cnt);
}