题解 | 正则表达式匹配

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

int main() {
    string s, p;
    cin >> s;
    cin >> p;
    int n = s.size(), m = p.size();

    auto same = [&](char a, char b) {
        return b == '.' || a == b;
    };

    vector<char> prev(m + 1, 0), cur(m + 1, 0);
    prev[0] = 1;                                    // 空串匹配空模式
    for (int j = 2; j <= m; ++j)                    // 处理 a*, a*b*, ...
        if (p[j - 1] == '*') prev[j] = prev[j - 2];

    for (int i = 1; i <= n; ++i) {
        fill(cur.begin(), cur.end(), 0);
        for (int j = 1; j <= m; ++j) {
            if (p[j - 1] != '*') {
                cur[j] = prev[j - 1] && same(s[i - 1], p[j - 1]);
            } else { // '*'：匹配0次 或 多次
                cur[j] = cur[j - 2] || ( same(s[i - 1], p[j - 2]) && prev[j] );
            }
        }
        swap(prev, cur);
    }

    cout << (prev[m] ? "true" : "false") << '\n';
    return 0;
}