Codeforces Round #138 (Div. 1) A : Bracket Sequence

問題概要

丸括弧と角括弧の列(L<1e5)の文字列が与えられる。括弧の対応がとれている部分文字列で、角括弧をもっとも多く含むものを具体的に求める問題。

解法

丸括弧と角括弧をそれぞれスタックに積んでいく。途中で括弧が足りなくなったり、対応してないものに当たったりしたら全部クリアすればよい。

acceptされたコード

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;

template<typename numType>
inline bool updateMax(numType& old, const numType& test) {
	if (old < test) {
		old = test;
		return true;
	}
	return false;
}

const int MAX_L = int(1e5);
char buf[MAX_L + 1];
int prevs[MAX_L + 1];
int accum[MAX_L + 1];

void init() {
	scanf("%s", buf);
}

void print(int maxi, int start, int last) {
	if (maxi <= 0) {
		puts("0\n");
		return ;
	}
	else {
		printf("%d\n", maxi);
		for (int i = start; i < last; ++i) {
			putchar(buf[i]);
		}
		puts("");
	}
}

void solve() {
	const int L = strlen(buf);
	for (int i = 0; i < L; ++i) {
		accum[i+1] = accum[i] + (buf[i] == '[' ? 1 : 0);
	}
	int maxi = 0, start = -1, last = -1;
	memset(prevs, -1, sizeof(prevs));

	stack<int> S1, S2;

	for (int i = 0; i < L; ++i) {
		const char c = buf[i];
		if (c == '[') {
			S1.push(i);
		}
		else if (c =='(') {
			S2.push(i);
		}
		else if(c == ']') {
			if (!S1.empty() && (S2.empty() || S2.top() < S1.top())) {
				prevs[i] = S1.top();
				S1.pop();
			}
			else {
				for (;!S1.empty();S1.pop()) ;
				for (;!S2.empty();S2.pop()) ;
			}
		}
		else if(c == ')') {
			if (!S2.empty() && (S1.empty() || S1.top() < S2.top())) {
				prevs[i] = S2.top();
				S2.pop();
			}
			else {
				for (;!S1.empty();S1.pop()) ;
				for (;!S2.empty();S2.pop()) ;
			}
		}
	}

	for (int i = L - 1 ; i >= 0; --i) {
		int l = prevs[i];
		for (;l != -1 && l > 0 && prevs[l-1] != -1; l = prevs[l-1]);
		if (l != -1) {
			if (updateMax(maxi, accum[i+1] - accum[l])) {
				start = l;
				last = i + 1;
			}
			i = l - 1;
		}
	}

	print(maxi, start, last);
}


int main() {
	init();
	solve();
	return 0;
}