合法括号式的最大长度求法(没优先级时)

合法括号式的最大长度求法(没有优先级时)

简单DP,求最长合法子串以及合法子串的个数，dp[i]代表以i为结尾最长的合法子串，（的dp值都是0，（的长度计入要看是否有），当读入一个）时，如果它左相邻的符号是（，该）的dp值加二，此时还要判断这段（）相邻的左面是否也是合法的，比如（）（）的情况，给它们标号1，2,3,4，此时dp[4]=2,dp[3]=0,dp[2]=2,dp[1]=0,要向前跳过上一段合法串，即dp[i-1],这里是0，因为从i往回走，还要走过当前已配对的（），所以上一段的末尾（如果‘（’左相邻的一段合法）就是dp[i-dp[i-1]-2],即dp[2],在加上上一段，即dp[4]=dp[4]+dp[4-0-2]=4；当读入一个）时，若左面不相邻（而是一段合法的串，如（（（）））此时i=6，dp[5]=4,就要找dp[i-dp[i-1]-1]，即上一个合法串的前一个，若是（,则dp[i]=2+dp[i-1]；当新读入的）的前一个既不是（也不是合法串，就是空闲的），该）空闲无法构成串，dp[i]=0没有改变括号东东

Time Limit: 1000MS Memory limit: 65536K

题目描述

        已知给出若干个只包含 “（”  或者  “）”字符串str！字符串的长度小于等于100W！求最长合法子串以及合法子串的个数！！

合法字串的格式要求如下：

1.  “()”

2.  “(())()”

3. “(()(()))”

不合法的情况如：

1. “)(”

2. “(()”

3. “(()))(”

4.......

输入

       输入包含若干组测试数据，每组为一行字符串。

输出

对于每组测试数据,输出最长合法子串以及合法子串的个数（如果最长合法子串为0，那么输出 0 1）！

示例输入

))()((())))(()())

示例输出

0 16 2

#include<stdio.h>#include<string.h>char str[1000015];int dp[1000015];int ans,num;int main(){    while(scanf("%s",str)!=EOF)    {        int len=strlen(str);        dp[0]=0;        ans=0;num=1;        for(int i=1; i<len; i++)        {            dp[i]=0;    //(()  )  <===i            if( i-dp[i-1]-1>=0 && str[i]==')' && str[i-dp[i-1]-1]=='(' )            {                 dp[i]=dp[i-1]+2;                if(i-dp[i-1]-2>=0&&dp[i-dp[i-1]-2])//(())()                {                    dp[i]+=dp[i-dp[i-1]-2];                }            }            if(ans<dp[i])   //更新长度，每次更新后数量变成1            {                ans=dp[i];                num=1;            }            else if(ans==dp[i]&&ans)  //计数            num++;        }        printf("%d %d\n",ans,num);    }    return 0;}

查看更多 下一篇