Codeforces 138A (226A) Bracket Sequence

問題

'(', ')', '[', ']'からなる文字列が与えられる。
この文字列の連続する部分文字列のうち、
括弧の対応が正しいもので、'['の含まれる個数が最大であるものをどれか一つ出力せよ。

制約条件

文字列の長さ≦10^5

方針

括弧の対応が取れてるかは適当にスタックを使って判定できる。
開き括弧が出てきたら、その種類と位置をスタックに積み、
閉じ括弧が出てきたら、スタックのトップが対応する開き括弧かどうかを見た後ポップすればいい。

スタックをもう一つ使って、最後に出来た対応の取れた極大な文字列の位置を入れておく。
閉じ括弧が出たときに、スタックを更新できるだけする。

ソースコード

string s;
vector<pair<pi, int> > lr;
vi v;

int main(){
	cin >> s;
	int ans = 0;
	int al = 0, ar = -1;
	
	rep(i, s.size()){
		if(s[i] == '(') v.pb(i);
		else if(s[i] == '[') v.pb(i + inf);
		else if(s[i] == ')' && v.size() && v.back() < inf ||
			s[i] == ']' && v.size() && v.back() >= inf
		){
			int l = v.back() % inf, r = i;
			int cnt = s[i] == ']';
			
			v.pop_back();
			
			while(lr.size() && (lr.back().first.second == l - 1 ||
				l <= lr.back().first.first)
			){
				//今出来た文字列が、前に作った文字列を含む場合か、連結できる場合
				//直前の文字列と、今できた括弧の文字列が連結できるとき、連結してしまう
				if(lr.back().first.second == l - 1){
					l = lr.back().first.first;
				}
				cnt += lr.back().second;
				lr.pop_back();
			}
			//文字列をこれ以上拡大できなくなったらスタックに入れておく。
			//ついでに答えも更新
			lr.pb(mp(mp(l, r), cnt));
			if(cnt > ans){
				ans = cnt;
				al = l; ar = r;
			}
		}
		else{
			v.clear();
		}
	}
	cout << ans << endl;
	cout << s.substr(al, ar - al + 1) << endl;
	return 0;
}