基础括号匹配学习笔记

发布时间:2024年01月14日

前言

括号匹配,是 OI 选手的基础。

本文也发表于洛谷:https://www.luogu.com.cn/blog/stripe-python/ji-chu-kuo-hao-pi-pei-xue-xi-bi-ji

Example 1

P1944

题意

给定一个字符串,求出其最长的匹配子串并输出。

题解

模板题目。这里我介绍一种很模板的写法:

我们用 o k i ok_i oki? 表示第 i i i 位是否可以被匹配。借助一个栈,可以很容易地求出 o k ok ok 数组:

stack<pair<char, int>> st;

for (int i = 1; i <= n; i++) {
	if (!st.empty() && ((st.top().first == '(' && s[i] == ')') || (st.top().first == '[' && s[i] == ']'))) {
		ok[i] = ok[st.top().second] = true;
		st.pop();
	} else {
		st.push(make_pair(s[i], i));
	}
}

接下来在 o k ok ok 数组中找最长的连续的 true 即可。注意设置 v i s vis vis 数组保证 O ( n ) O(n) O(n) 复杂度。

AC 代码如下:

#include <bits/stdc++.h>
#define N 1000005
using namespace std;

char s[N];
stack<pair<char, int>> st;
bool ok[N], vis[N];

int main() {
	scanf("%s", s + 1);
	int n = strlen(s + 1);
	for (int i = 1; i <= n; i++) {
		if (!st.empty() && ((st.top().first == '(' && s[i] == ')') || (st.top().first == '[' && s[i] == ']'))) {
			ok[i] = ok[st.top().second] = true;
			st.pop();
		} else {
			st.push(make_pair(s[i], i));
		}
	}
	int l = 0, r = 0;
	for (int i = 1; i <= n; i++){
		if (!ok[i] || vis[i]) continue;
		int tl = i, tr = i;
		for (int j = i; j <= n; j++) {
			if (!ok[j]) break;
			vis[j] = true;
			tr = j;
		}
		if (r - l < tr - tl) l = tl, r = tr;
	}
	if (l == 0) return 0; 
	//printf("%d\n", r - l + 1);
	for (int i = l; i <= r; i++) putchar(s[i]);
	return 0;
}

这个板子还是很容易理解和记忆的。

Example 2

NFLS 1858 B

题意

给定一个字符串,求出其 [ 最多的匹配子串并输出。

题解

用上面的模板模拟即可。使用前缀和快速统计区间内 [ 的个数。

AC 代码:

#include <bits/stdc++.h>
#define N 100005
using namespace std;

char s[N];
stack<pair<char, int>> st;
bool ok[N], vis[N];
int cnt[N];

int main() {
	scanf("%s", s + 1);
	int n = strlen(s + 1);
	for (int i = 1; i <= n; i++) {
		if (!st.empty() && ((st.top().first == '(' && s[i] == ')') || (st.top().first == '[' && s[i] == ']'))) {
			ok[i] = ok[st.top().second] = true;
			st.pop();
		} else {
			st.push(make_pair(s[i], i));
		}
	}
	//for (int i = 1; i <= n; i++) cout << ok[i];
	for (int i = 1; i <= n; i++) {
		cnt[i] = cnt[i - 1] + (s[i] == '[');
	}
	int l = 1, r = 1;
	for (int i = 1; i <= n; i++){
		if (!ok[i] || vis[i]) continue;
		int tl = i, tr = i;
		for (int j = i; j <= n; j++) {
			if (!ok[j]) break;
			vis[j] = true;
			tr = j;
		}
		if (cnt[r] - cnt[l - 1] <= cnt[tr] - cnt[tl - 1]) l = tl, r = tr;
	}
	if (l == r) return puts("0"), 0;
	printf("%d\n", cnt[r] - cnt[l - 1]);
	for (int i = l; i <= r; i++) putchar(s[i]);
	return 0;
}

Example 3

找不到这道题,所以自己造了一个 U397404

题意

给定一个字符串和 q q q 次询问,每次查询 s [ l . . . r ] s[l...r] s[l...r] 是否合法。

题解

看看题目要求什么。显然需要在 O ( n ) O(n) O(n) 时间内解决,我们先跑一遍模板获得 o k ok ok 数组。

查询转变为 o k [ l . . . r ] ok[l...r] ok[l...r] 是否全部为 true

可以运用一个巧妙的前缀和,记 s u m sum sum o k ok ok 的前缀和,只需要判断 s u m r ? s u m l ? 1 sum_r-sum_{l-1} sumr??suml?1? 是否为 r ? l + 1 r - l + 1 r?l+1 即可。

std 如下:

#include <bits/stdc++.h>
#define N 1000005
using namespace std;

int n, q, l, r;
char s[N];
stack<pair<char, int>> st;
bool ok[N];
int cnt[N];

int main() {
	scanf("%d %d", &n, &q);
	scanf("%s", s + 1);
	for (int i = 1; i <= n; i++) {
		if (!st.empty() && ((st.top().first == '(' && s[i] == ')') || (st.top().first == '[' && s[i] == ']'))) {
			ok[i] = ok[st.top().second] = true;
			st.pop();
		} else {
			st.push(make_pair(s[i], i));
		}
	}
	for (int i = 1; i <= n; i++) cnt[i] = cnt[i - 1] + ok[i];
	while (q--) {
		scanf("%d %d", &l, &r);
		puts(cnt[r] - cnt[l - 1] == r - l + 1 ? "Yes" : "No");
	}
	return 0;
}
文章来源:https://blog.csdn.net/weixin_38805653/article/details/135585825
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。