题解 P1944 最长括号匹配_NOI导刊2009提高（1）

栈，模拟

把每个元素逐个入栈
如果和栈顶元素匹配，那么一块弹出去，同时标记这里是可匹配的。
取出连续的，最长的可匹配的序列即可。

#include <iostream>

#include <stdio.h>

#include <string.h>

#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 ;

}

巴特西

题解 P1944 最长括号匹配_NOI导刊2009提高（1）

最新文章

热门文章