1 /* 2     题意：求最长括号匹配的长度和它的个数 3     贪心+stack：用栈存放最近的左括号的位置，若是有右括号匹配，则记录它们的长度，更新最大值，可以在O (n)解决 4     详细解释：http://blog.csdn.net/taoxin52/article/details/26012167 5 */ 6 #include 
     
       7 #include 
      
        8 #include 
       
         9 #include 
        
         10 #include 
         
          11 using namespace std;12 13 const int MAXN = 1e6 + 10;14 const int INF = 0x3f3f3f3f;15 char s[MAXN];16 int len[MAXN];17 stack
          
            S;18 19 int main(void) //Codeforces Beta Round #5 C. Longest Regular Bracket Sequence20 {21 // freopen ("C.in", "r", stdin);22 23 while (scanf ("%s", s) == 1)24 {25 while (!S.empty ()) S.pop ();26 memset (len, 0, sizeof (len));27 28 int mx = 0; int cnt = 0;29 for (int i=0; s[i]; ++i)30 {31 if (s[i] == '(') S.push (i);32 else33 {34 if (!S.empty ())35 {36 int p = S.top (); S.pop ();37 len[i] = (p > 0 ? len[p-1] : 0) + (i - p + 1);38 }39 }40 if (len[i] > mx) {mx = len[i]; cnt = 1;}41 else if (len[i] == mx) {cnt++;}42 }43 44 if (mx == 0) puts ("0 1");45 else printf ("%d %d\n", mx, cnt);46 }47 48 return 0;49 }