CodeForces 5C. Longest Regular Bracket Sequence
C. 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 106.
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".
)((())))(()())
output
6 2
input
))(
output
0 1
まずすべてのデータを累積し、'('は-1を表し、')'は1を表します.
このときdataのデータを関数画像として想像することができ、以下は横座標として、本題はこの画像の2つの等しい関数値の最大横座標距離を求める(この2点の間のすべての関数値がこの2点の関数値以下であることを前提とする).
#include<iostream>
#include<cstdio>
using namespace std;
int len,cur,s,ans_len,ans_sum;
char c[1000005];
int data[1000005];
int main(){
while(scanf("%c",&c[1])!=EOF){
cur = 1;
data[0]=0;
do{
if(c[cur]!='
') {
if(c[cur]=='(') data[cur] = data[cur-1] - 1;
else if(c[cur]==')') data[cur] = data[cur-1] + 1;
cur++;
scanf("%c",&c[cur]);
}
else break;
}while(1);
ans_len=len=s=ans_sum=0;
for(int i=1;i<cur;i++) {
if(data[i]>data[s]) {
s = i;
if(ans_len<len) {
ans_len = len;
ans_sum = 1;
}
else if(ans_len==len&&len!=0) {
ans_sum++;
}
len = 0;
}
else {
len++;
}
}
if(data[cur-1]==data[s]) {
if(ans_len==0) ans_len = len;
if(cur-1-s==ans_len) ans_sum++;
}
else if(data[cur-1]<data[s]) {
for(int i=1;i<=cur-s;i++) {
if(c[cur-i]==')') data[i]=data[i-1] - 1;
else if(c[cur-i]=='(') data[i]=data[i-1] + 1;
}
cur = cur-s+1;
s = len = 0;
for(int i=1;i<cur;i++) { // ！！！！ ！！！！！
if(data[i]>data[s]) {
s = i;
if(ans_len<len) {
ans_len = len;
ans_sum = 1;
}
else if(ans_len==len&&len!=0) {
ans_sum++;
}
len = 0;
}
else {
len++;
}
}
}
if(ans_len==0) ans_sum=1;
printf("%d %d
",ans_len,ans_sum);
}
}