栈,模拟
- 把每个元素逐个入栈
- 如果和栈顶元素匹配,那么一块弹出去,同时标记这里是可匹配的。
- 取出连续的,最长的可匹配的序列即可。
#include#include #include #define re register#define Clean(X,K) memset(X,K,sizeof(X))using namespace std ;const int Maxl = 1000005 ;string S ;char A[Maxl] ;int Ans = 0 , Now = 0 , Top = 1 , M[Maxl] , Lc[Maxl] , From;int main () {// freopen ("P1944.in" , "r" , stdin) ; getline (cin , S) ; int L = S.length() ; Clean(M , 0) , Clean(A , 0); for (re int i = 0 ; i < L ; ++ i) { if (S[i] == ')' && A[Top] == '(' ) { -- Top , M[i] = M[Lc[Top + 1]] = 1 ; continue ; } if (S[i] == ']' && A[Top] == '[' ) { -- Top , M[i] = M[Lc[Top + 1]] = 1 ; continue ; } A[++ Top] = S[i] ; Lc[Top] = i ; } for (re int i = 0 ; i < L; ++ i) { if (M[i]) ++ Now ; else { if (Now > Ans) { Ans = Now ; From = i - 1 ; } Now = 0 ; } } int St=0; for (re int i = From ; i >= 0 ; -- i ) if (!M[i]) { St = i + 1; break ; }; for (re int i = St ; i <= From ; ++ i) putchar(S[i]) ; fclose (stdin) , fclose (stdout) ; return 0 ;}