基础括号匹配学习笔记

· · 个人记录

前言

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

Example 1

P1944

题意

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

题解

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

我们用 ok_i 表示第 i 位是否可以被匹配。借助一个栈，可以很容易地求出 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));
    }
}

接下来在 ok 数组中找最长的连续的 true 即可。注意设置 vis 数组保证 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

AT_abc350_f。

题意

给定给一个字符串，其中含有很多括号，括号里的内容会被翻转和变换大小写，输出这个字符串去掉括号的结果。

题解

以这道题为例，我介绍第二种模板：

用栈记录上一个左括号，遇到右括号则出栈，这样记录下每一个匹配的下标对。

然后用文艺平衡树维护即可。复杂度 O(n \log n)。

// -DSPN_LOCAL -Wl,--stack=104857600
#include <bits/stdc++.h>
using namespace std;

// fhq启动
template <class T>
class SegmentFHQTreap {
private:
    struct node {
        T val;
        int prio, cnt, size;
        node *left, *right;
        bool rev;

        node(const T& v) : val(v), prio(rand()), cnt(1), size(1),
        left(nullptr), right(nullptr), rev(false) {}

        node* pushup() {
            size = cnt + (left ? left->size : 0) + (right ? right->size : 0);
            return this;
        }

        void pushdown() {
            if (!rev) return; 
            val = islower(val) ? toupper(val) : tolower(val);
            swap(left, right);
            if (left) left->rev ^= 1;
            if (right) right->rev ^= 1;
            rev = false;
        }
    };
    node *root;

    pair<node*, node*> split(node* x, int sz) {
        if (!x) return make_pair(nullptr, nullptr);
        x->pushdown();
        int ls = x->left ? x->left->size : 0;
        if (sz <= ls) {
            auto l = split(x->left, sz);
            x->left = l.second, x->pushup();
            return make_pair(l.first, x);
        }
        auto r = split(x->right, sz - ls - 1);
        x->right = r.first, x->pushup();
        return make_pair(x, r.second);
    }

    node* merge(node *a, node *b) {
        if (!a || !b) return a ? a : b;
        a->pushdown(), b->pushdown();
        return (a->prio < b->prio) ? (a->right = merge(a->right, b), a->pushup())
            : (b->left = merge(a, b->left), b->pushup());
    }

public:
    SegmentFHQTreap() : root(nullptr) {srand(time(NULL));}
    bool empty() const {return root;}
    int size() const {return root->size;}

    void insert(int idx, const T& val) {
        auto t = split(root, idx), ltr = split(t.first, idx);
        node* ls = merge(ltr.first, ltr.second ? ltr.second : new node(val));
        root = merge(ls, t.second);
    }
    void reverse(int l, int r) {
        auto ls = split(root, l - 1), gt = split(ls.second, r - l + 1);
        gt.first->rev = true;
        root = merge(ls.first, merge(gt.first, gt.second));
    }

    vector<T> inorder() {
        vector<T> res; res.reserve(root->size);
        function<void(node*)> dfs = [&](node* x) -> void {
            if (!x) return;
            x->pushdown(), dfs(x->left), res.emplace_back(x->val), dfs(x->right);
        };
        return dfs(root), res;
    }
};
SegmentFHQTreap<char> fhq;

#define N 500005
int n;
char s[N];
vector<pair<int, int>> q;
stack<int> st;

void _main() {
    cin >> (s + 1);
    n = strlen(s + 1);
    for (int i = 1; i <= n; i++) {
        fhq.insert(i - 1, s[i]);
    } 

    for (int i = 1; i <= n; i++) {
        if (s[i] == '(') st.emplace(i);
        else if (s[i] == ')') {
            q.emplace_back(st.top(), i);
            st.pop();
        }
    }
    for (auto info : q) {
        fhq.reverse(info.first, info.second);
    } 
    for (char i : fhq.inorder()) {
        if (i != '(' && i != ')') cout << i;
    }
} signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr), cerr.tie(nullptr);

    int t = 1;
//  cin >> t;
    while (t--) _main();
    return 0;
}