C. Longest Regular Bracket Sequence
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
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".
Sample test(s)
input
)((())))(()())
output
6 2
input
))(
output
0 1
Explanation
First of all, for each closing bracket in our string let's define 2 values:
- d[j] = position of corresponding open bracket, or -1 if closing bracket doesn't belong to any regular bracket sequence.
- c[j] = position of earliest opening bracket, such that substring s(c[j], j) (both boundaries are inclusive) is a regular bracket sequence. Let's consider c[j] to be -1 if closing bracket doesn't belong to any regular bracket sequence.
- Iterate through the characters of the string.
- If current character is opening bracket, put its position into the stack.
- If current character is closing bracket, there are 2 subcases:
- Stack is empty - this means that current closing bracket doesn't have corresponding open one. Hence, both d[j] and c[j] are equal to -1.
- Stack is not empty - we will have position of the corresponding open bracket on the top of the stack - let's put it to d[j] and remove this position from the stack. Now it is obvious, that c[j] is equal at least to d[j]. But probably, there is a better value for c[j]. To find this out, we just need to look at the position d[j] - 1. If there is a closing bracket at this position, and c[d[j] - 1] is not -1, than we have 2 regular bracket sequences s(c[d[j] - 1], d[j] - 1) and s(d[j], j), which can be concatenated into one larger regular bracket sequence. So we put c[j] to be c[d[j] - 1] for this case.
Code
#include<bits/stdc++.h>
using namespace std;
int c[2000100];
int d[2000100];
stack<int> st;
int main()
{
string s;
cin>>s;
int l=s.length();
int b=0;
int al=-1,ar=-1;
int ans=0;
int res=0;
int cnt=0;
memset(d,-1,sizeof(d));
memset(c,-1,sizeof(c));
for(int i=1;i<=l;i++)
{
if(s[i-1]=='(')
st.push(i);
else
{
if(st.empty())
{
c[i]=-1;
d[i]=-1;
}
else
{
int val=st.top();
st.pop();
d[i]=val;
c[i]=val;
if(d[i]-1>=1 && s[d[i]-2]==')' && c[d[i]-1]!=-1)
{
// cout<<"i here "<<d[i]-1<<" "<<c[d[i]-1]<<endl;
c[i]=min(c[i],c[d[i]-1]); }
}
}
}
// for(int i=1;i<=l;i++)
// cout<<c[i]<<" ";
// cout<<endl;
ans=0;
for(int i=1;i<=l;i++)
{
if(c[i]!=-1)
ans=max(ans,(i-c[i]+1));
}
if(ans==0)
{
cout<<"0 1"<<endl;
return 0;
}
else
{
int cnt=0;
for(int i=1;i<=l;i++)
{
if(c[i]!=-1)
if(i-c[i]+1==ans)
cnt++;
}
cout<<ans<<" "<<cnt<<endl;
}
return 0;
}
