51nod 1478 括号序列的最长合法子段 - dblank

51nod 1478 括号序列的最长合法子段

这里有另一个关于处理合法的括号序列的问题。

如果插入“+”和“1”到一个括号序列,我们能得到一个正确的数学表达式,我们就认为这个括号序列是合法的。例如,序列"(())()", "()"和"(()(()))"是合法的,但是")(", "(()"和"(()))("是不合法的。

这里有一个只包含“(”和“)”的字符串,你需要去找到最长的合法括号子段,同时你要找到拥有最长长度的子段串的个数。

Input
第一行是一个只包含“(”和“)”的非空的字符串。它的长度不超过 1000000。
Output
输出合格的括号序列的最长子串的长度和最长子串的个数。如果没有这样的子串,只需要输出一行“0  1”。
Input示例
)((())))(()())
Output示例

6 2

思路:一段子串和是(和)的数量一样,并且开头是(结尾是)。我们可以强行让一个)和最近的一个(匹配,匹配过的就标记不在匹配,我们可以将(的位置放在一个stack里面,这样就可以和最近的匹配。最后统计的时候,只要有一段连续被标记过,那一段就是合法的,直接匹配最长的。

#include <bits/stdc++.h>  
using namespace std;  
typedef long long ll;  
int INF = 0x3f3f3f3f;  
const int N = 1e6 + 10;  
char s[N];  
int vis[N];  
int main()  
{  
    scanf("%s", s+1);  
    memset(vis, 0, sizeof(vis));  
    stack<int>sta;  
    int l = strlen(s+1), maxx , tmp, a = 0;  
    for(int i = 1; i<=l; i++)  
    {  
        if(s[i] == '(')  
            sta.push(i);  
        else  
        {  
            if(!sta.empty())  
            {  
                vis[i] = 1;  
                vis[sta.top()] = 1;  
                sta.pop();  
            }  
        }  
    }  
    tmp = maxx = 0;  
    for(int i = 1; i<=l; i++)  
    {  
       if(vis[i])  
       {  
           tmp++;  
       }  
       else  
       {  
            tmp = 0;  
       }  
       if(tmp == maxx)  
        a++;  
       else if(tmp > maxx)  
        a = 1, maxx = tmp;  
    }  
    if(maxx == 0)  
        cout<<0<<" "<<1<<endl;  
    else  
    cout<<maxx<< " "<<a<<endl;  
    return 0;  
}  

 

相关文章

发表新评论