括號東東 Time Limit: 1000MS Memory limit: 65536K 題目描述 已知給出若干個只包含 “（” 或者 “）”字符串str！字符串的長度小於等於100W！求最長合法子串以及合法子串的個數！！ 合法字串的格式要求如下： 1. “()” 2. “(())()” 3. “(()(()))” 不合法的情況如： 1. “)(” 2. “(()” 3. “(()))(” 4....... 輸入 輸入包含若干組測試數據，每組為一行字符串。 輸出 對於每組測試數據,輸出最長合法子串以及合法子串的個數（如果最長合法子串為0，那麼輸出 0 1）！ 示例輸入 ))()((())))(()()) 示例輸出 0 16 2 提示 來源 Azheng@SDJZU 示例程序 這是我們周賽的一道題目，現在看來幾乎是最簡單的了，這道題目題意表述不清，尤其輸出最後讓求合法字串的個數的時候，這是這個題目的錯誤所在，其實這題目讓求的是最長合法字串的個數，我一開始就按照求合法字串的個數來做的，可是卻是一次又一次的WA，哎，最後問了別人，才知道這題目最後求的是最長合法字串的個數。 其實這道題目求所有合法字串的個數也是一個很不錯的題目，求最長合法合法字串的個數，就把這個題目弄的有些簡單了。 [cpp] #include <stdio.h> #include <string.h> #include <math.h> char s1[1000000]; char statck[1000000]; struct num { int pos; char c; }b[1000000]; int main() { int i,j,n,m,s,t,l,top,k,res,max; while(scanf("%s",s1)!=EOF) { l=strlen(s1); top=0; for(i=0;i<=l-1;i++) { if(s1[i]=='(') { b[top].pos=i; b[top++].c='('; }else if(s1[i]==')') { if(top>0&&b[top-1].c=='(') { top-=1; }else { top=0; } } } for(i=top-1;i>=0;i--) { s1[b[i].pos]=')'; } top=0; max=0; res=0; k=0; for(i=0,s=0;i<=l-1;i++) { if(s1[i]=='(') { statck[top++]='('; }else if(s1[i]==')') { if(top>0&&statck[top-1]=='(') { s+=2; top-=1; k=1; }else { if(max<s&&k==1) { max=s; s=0; res=1; }else if(max==s&&k==1) { res++; s=0; } s=0; top=0; k=0; } } } if(k==1) { if(max<s) { max=s; res=1; }else if(max==s) { res++; } } if(max!=0) { www.2cto.com printf("%d %d\n",max,res); }else { printf("0 1\n"); } } return 0; }
