i.cpp

ACM训练题解 最新版 共8题 ACM训练题解 最新版 共8题

// Problem I
// http://acm.zju.edu.cn/show_problem.php?pid=2704
// Solution by semiconductor
#include	<cstdio>
#include	<cstdlib>
#include	<cstring>

using namespace std;
const char NUL = '\0';

const int N = 100000;

char buf[N + 2];
int S[N + 1];
char rev[128];

void
Solve(void)
{
	S[0] = 0;
	int ns = 0;
	int best = 0, mp = 0;
	for ( int i = 1; buf[i]; i++ ) {
		char c = buf[i];
		if ( rev[c] == 0 ) S[++ns] = i;
		else {
			if ( rev[c] == buf[S[ns]] ) {
				--ns;
				if ( i - S[ns] > best ) {
					best = i - S[ns];
					mp = S[ns] + 1;
				}
			} else
				S[++ns] = i;
		}
	}
	printf("%.*s\n", best, buf + mp);
}

int
main()
{
	rev[']'] = '[';
	rev[')'] = '(';
	buf[0] = '#';
	while ( scanf("%s", buf + 1) != EOF ) {
		Solve();
		printf("\n");
	}
}