第十一届中国大学生程序设计竞赛网络预选赛（CCPC Online 2025）——通配符匹配

思路讲解

难点其实就在与这个想到把

vector<vll> valids(SZ(seg));
FOR(i, 0, SZ(seg) - 1) {
    auto [hs, len] = seg[i];
    FOR(j, 0, SZ(s) - 1) {
        if (len + j - 1 >= SZ(s)) {
            break;
        }
        ll r = len + j - 1;
        if (cal(hss, j, r) == hs) {
            valids[i].PB(j);
        }
    }
    if (valids[i].empty()) {
        cout << 0 << "\n";
        return;
    }
}
// 特判没有*的情况
if (!have) {
    cout << SZ(valids[0]) << "\n";
    return;
}
ll ans = 0;
// *之间的这个长度是一定的
if (t.back() == '*' && t.front() == '*') {
    ll on = SZ(s) - 1;
    ROF(i, SZ(valids.back()) - 1, 0) {
        ll p = valids.back()[i];
        bool ok = true;
        ll up = p;
        ROF(j, SZ(seg) - 2, 0) {
            ll len = seg[j][1];
            auto it = upper_bound(all(valids[j]), up - len);
            if (it == valids[j].begin()) {
                ok = false;
                break;
            }
            it--;
            up = *it;
        }
        if (!ok) {
            continue;
        }
        ll ed = p + seg.back()[1] - 1;
        ans += (up - 0 + 1) * (on - ed + 1);
        on = ed - 1;
    }
} else if (t.back() == '*') {
    ll on = SZ(s) - 1;
    ROF(i, SZ(valids.back()) - 1, 0) {
        ll p = valids.back()[i];
        bool ok = true;
        ll up = p;
        ROF(j, SZ(seg) - 2, 0) {
            ll len = seg[j][1];
            auto it = upper_bound(all(valids[j]), up - len);
            if (it == valids[j].begin()) {
                ok = false;
                break;
            }
            it--;
            up = *it;
        }
        if (!ok) {
            continue;
        }
        ll ed = p + seg.back()[1] - 1;
        auto t = lower_bound(all(valids[0]), up) - valids[0].begin() + 1;
        ans += t * (on - ed + 1);
        on = ed - 1;
    }
} else if (t.front() == '*') {
    for (auto p : valids.back()) {
        bool ok = true;
        ll up = p;
        ROF(j, SZ(seg) - 2, 0) {
            ll len = seg[j][1];
            auto it = upper_bound(all(valids[j]), up - len);
            if (it == valids[j].begin()) {
                ok = false;
                break;
            }
            it--;
            up = *it;
        }
        if (!ok) {
            continue;
        }
        ans += up - 0 + 1;
    }
} else {
    for (auto p : valids.back()) {
        bool ok = true;
        ll up = p;
        ROF(j, SZ(seg) - 2, 0) {
            ll len = seg[j][1];
            auto it = upper_bound(all(valids[j]), up - len);
            if (it == valids[j].begin()) {
                ok = false;
                break;
            }
            it--;
            up = *it;
        }
        if (!ok) {
            continue;
        }
        auto t = lower_bound(all(valids[0]), up) - valids[0].begin() + 1;
        ans += t;
    }
}
cout << (long long)ans;

AC代码

https://qoj.ac/submission/1395803

源代码

// by Gospel_rock
#include <algorithm>
#include <bits/stdc++.h>
#include <vector>
#define all(vec) vec.begin(), vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var << ":" << var << "\n";
#define cend cerr << "\n-----------\n"
#define fsp(x) fixed << setprecision(x)
#define minn(vec) *min_element(vec.begin(), vec.end())
#define maxx(vec) *max_element(vec.begin(), vec.end())
#define yyy cout << "YES\n"
#define nnn cout << "NO\n"

using namespace std;
#ifdef LOCAL
template <typename T> void _print(T x) { cerr << x; }
// 可以打印多层数组，但是格式不是很好
template <typename T> void _print(vector<T> v) {
    cerr << "[ ";
    for (T i : v)
        _print(i), cerr << " ";
    cerr << "]";
}
template <typename T> void _print(set<T> s) {
    cerr << "{ ";
    for (T i : s)
        _print(i), cerr << " ";
    cerr << "}";
}
template <typename T, typename U> void _print(pair<T, U> p) {
    cerr << "{";
    _print(p.first);
    cerr << ", ";
    _print(p.second);
    cerr << "}";
}
template <typename T, typename U> void _print(map<T, U> m) {
    cerr << "{ ";
    for (auto &p : m)
        _print(p), cerr << " ";
    cerr << "}";
}
// 打印两层数组，格式好一些
template <typename T> void _print(vector<vector<T>> v) {
    cerr << "{\n";
    for (auto i : v)
        _print(i), cerr << "\n";
    cerr << " }";
}
#endif

using ll = __int128_t;
using ull = unsigned long long;
using DB = double;
using LD = long double;
using pdd = pair<DB, DB>;
using plb = pair<ll, bool>;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vb = vector<bool>;
using tll = tuple<ll, ll, ll>;
using vii = vector<int>;
using vpll = vector<pll>;
using vtll = vector<tll>;
using vdb = vector<DB>;
using vc = vector<char>;
using arr3 = array<ll, 3>;
using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)5e5 + 10,
                    INF = (ll)1e17 + 3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod = (ll)1e9 + 7;  // 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
constexpr ll base = 233;
ll N, M, Q, X, K, T, lT;

inline void __();
ll Base[MAXN];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Base[0] = 1;
    FOR(i, 1, MAXN - 5) { Base[i] = Base[i - 1] * base; }
    // cin >> lT;
    // while (lT--)
    __();
    return 0;
}
/*

*/
string t, s;
// hash 我们一般还是采用 1-based 方法写
ll cal(const vll &hs, ll l, ll r) {
    ll res = hs[r] - (l == 0 ? 0 : hs[l - 1] * Base[r - l + 1]);
    return res;
}
inline void __() {
    cin >> t >> s;
    vll hst(SZ(t) + 5), hss(SZ(s) + 5);
    FOR(i, 0, SZ(t) - 1) { hst[i] = (i == 0 ? 0 : hst[i - 1] * base) + t[i]; }
    FOR(i, 0, SZ(s) - 1) { hss[i] = (i == 0 ? 0 : hss[i - 1] * base) + s[i]; }
    bool have = false;
    FOR(i, 0, SZ(t) - 1) {
        if (t[i] == '*')
            have = true;
    }
    t += '*';
    ll up = 0;
    vector<arr2> seg;
    FOR(i, 0, SZ(t) - 1) {
        if (t[i] == '*') {
            if (up == i) {
                up = i + 1;
                continue;
            }
            seg.PB({cal(hst, up, i - 1), i - 1 - up + 1});
            up = i + 1;
        }
    }
    t.erase(prev(t.end()));
    if (seg.empty()) {
        cout << SZ(s) * (SZ(s) + 1) / 2 << "\n";
        return;
    }

    // FOR(i, 0, SZ(seg) - 1) {
    //     auto [hs, len] = seg[i];
    //     debug(hs);
    //     debug(len);
    // }
    // debug(SZ(seg));
    // debug(SZ(t));
    // debug(SZ(s));
    // ROF(i,SZ(t)-1,SZ(t)-10){
    //     cerr<<t[i];
    // }
    // cerr<<"\n";
    // debug(have);

    // 合法起始点
    vector<vll> valids(SZ(seg));
    FOR(i, 0, SZ(seg) - 1) {
        auto [hs, len] = seg[i];
        FOR(j, 0, SZ(s) - 1) {
            if (len + j - 1 >= SZ(s)) {
                break;
            }
            ll r = len + j - 1;
            if (cal(hss, j, r) == hs) {
                valids[i].PB(j);
            }
        }
        if (valids[i].empty()) {
            cout << 0 << "\n";
            return;
        }
    }
    // 特判没有*的情况
    if (!have) {
        cout << SZ(valids[0]) << "\n";
        return;
    }
    ll ans = 0;
    // *之间的这个长度是一定的
    if (t.back() == '*' && t.front() == '*') {
        ll on = SZ(s) - 1;
        ROF(i, SZ(valids.back()) - 1, 0) {
            ll p = valids.back()[i];
            bool ok = true;
            ll up = p;
            ROF(j, SZ(seg) - 2, 0) {
                ll len = seg[j][1];
                auto it = upper_bound(all(valids[j]), up - len);
                if (it == valids[j].begin()) {
                    ok = false;
                    break;
                }
                it--;
                up = *it;
            }
            if (!ok) {
                continue;
            }
            ll ed = p + seg.back()[1] - 1;
            ans += (up - 0 + 1) * (on - ed + 1);
            on = ed - 1;
        }
    } else if (t.back() == '*') {
        ll on = SZ(s) - 1;
        ROF(i, SZ(valids.back()) - 1, 0) {
            ll p = valids.back()[i];
            bool ok = true;
            ll up = p;
            ROF(j, SZ(seg) - 2, 0) {
                ll len = seg[j][1];
                auto it = upper_bound(all(valids[j]), up - len);
                if (it == valids[j].begin()) {
                    ok = false;
                    break;
                }
                it--;
                up = *it;
            }
            if (!ok) {
                continue;
            }
            ll ed = p + seg.back()[1] - 1;
            auto t = lower_bound(all(valids[0]), up) - valids[0].begin() + 1;
            ans += t * (on - ed + 1);
            on = ed - 1;
        }
    } else if (t.front() == '*') {
        for (auto p : valids.back()) {
            bool ok = true;
            ll up = p;
            ROF(j, SZ(seg) - 2, 0) {
                ll len = seg[j][1];
                auto it = upper_bound(all(valids[j]), up - len);
                if (it == valids[j].begin()) {
                    ok = false;
                    break;
                }
                it--;
                up = *it;
            }
            if (!ok) {
                continue;
            }
            ans += up - 0 + 1;
        }
    } else {
        for (auto p : valids.back()) {
            bool ok = true;
            ll up = p;
            ROF(j, SZ(seg) - 2, 0) {
                ll len = seg[j][1];
                auto it = upper_bound(all(valids[j]), up - len);
                if (it == valids[j].begin()) {
                    ok = false;
                    break;
                }
                it--;
                up = *it;
            }
            if (!ok) {
                continue;
            }
            auto t = lower_bound(all(valids[0]), up) - valids[0].begin() + 1;
            ans += t;
        }
    }
    cout << (long long)ans;
}
/*
AC
https://qoj.ac/submission/1395803

*ab*
abab

5
*/

心路历程（WA，TLE，MLE……）