首页 > 题解 > codeforce 5C Longest Regular Bracket Sequence

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


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×