第十一届中国大学生程序设计竞赛网络预选赛（CCPC Online 2025）——通配符匹配 · znzryb
## 思路讲解
难点其实就在与这个想到把
```cpp
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](https://qoj.ac/submission/1395803)
::: 源代码
```cpp
// 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……）