Wildcard Pattern Matching (verify/poly/wildcard.test.cpp)

• View this file on GitHub
• Last update: 2026-01-05 01:05:39+01:00
• Problem: https://judge.yosupo.jp/problem/wildcard_pattern_matching

Depends on

• cp-algo/math/cvector.hpp
• cp-algo/random/rng.hpp
• cp-algo/util/big_alloc.hpp
• cp-algo/util/checkpoint.hpp
• cp-algo/util/complex.hpp
• cp-algo/util/simd.hpp

Code

// @brief Wildcard Pattern Matching
#define PROBLEM "https://judge.yosupo.jp/problem/wildcard_pattern_matching"
#pragma GCC optimize("O3,unroll-loops")
#define CP_ALGO_CHECKPOINT
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#include "cp-algo/math/cvector.hpp"
#include "cp-algo/random/rng.hpp"

using namespace std;
using namespace cp_algo::math;

using fft::ftype;
using fft::point;
using fft::vftype;
using fft::cvector;

void semicorr(auto &a, auto &b) {
    a.fft();
    b.fft();
    a.dot(b);
    a.ifft();
}

auto is_integer(auto a) {
    static const ftype eps = 1e-9;
    return cp_algo::abs(a - cp_algo::round(a)) < eps;
}

cp_algo::big_string matches(cp_algo::big_string const& A, cp_algo::big_string const& B, char wild = '*') {
    static ftype project[2][128];
    static bool init = false;
    if(!init) {
        init = true;
        std::uniform_real_distribution<> dis(.5, 2.);
        for(int i = 0; i < 128; i++) {
            ftype x = dis(cp_algo::random::gen);
            project[0][i] = x;
            project[1][i] = 1. / x;
        }
    }
    project[0][(int)wild] = project[1][(int)wild] = 0;
    cp_algo::big_vector<cvector> P;
    P.emplace_back((size(A) + 1) / 2);
    P.emplace_back((size(A) + 1) / 2);
    auto N = P[0].size();
    auto assign = [&](int z) {
        return [&, z](auto ic) {
            auto [i, c] = ic;
            if(i < (int)N) {
                real(P[z].r[i / fft::flen])[i % fft::flen] = project[z][(int)c];
            } else {
                i -= N;
                imag(P[z].r[i / fft::flen])[i % fft::flen] = project[z][(int)c];
            }
        };
    };
    ranges::for_each(A | views::enumerate, assign(0));
    ranges::for_each(B | views::reverse | views::enumerate, assign(1));
    cp_algo::checkpoint("cvector fill");
    semicorr(P[0], P[1]);
    cp_algo::big_string ans(2 * size(P[0]), '0');
    auto start = (ssize(B) - 1) / fft::flen * fft::flen;
    for(auto j = start; j < size(ans); j += fft::flen) {
        decltype(is_integer(real(P[0].at(j)))) check;
        if(j < N) {
            check = is_integer(real(P[0].at(j)));
        } else {
            check = is_integer(imag(P[0].at(j - N)));
        }
        for(int z = 0; z < 4; z++) {
            ans[j + z] ^= (bool)check[z];
        }
    }
    cp_algo::checkpoint("fill answer");
    return ans.substr(size(B) - 1, size(A) - size(B) + 1);
}

void solve() {
    cp_algo::big_string a, b;
    cin >> a >> b;
    cp_algo::checkpoint("input");
    cout << matches(a, b) << "\n";
    cp_algo::checkpoint("output");
    cp_algo::checkpoint<true>("done");
}

signed main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) {
        solve();
    }
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj_resolve/resolver.py", line 181, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 252, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 327, in update
    assert len(lines) == len(uncommented_lines)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
AssertionError

Test cases

Env	Name	Status	Elapsed	Memory
g++	alternating_00	AC	12 ms	13 MB
g++	alternating_01	AC	13 ms	13 MB
g++	alternating_02	AC	5 ms	5 MB
g++	alternating_03	AC	11 ms	13 MB
g++	alternating_04	AC	11 ms	13 MB
g++	example_00	AC	4 ms	4 MB
g++	hack_998244353_00	AC	13 ms	14 MB
g++	hack_998244353_01	AC	12 ms	14 MB
g++	hack_998244353_02	AC	12 ms	14 MB
g++	random_00	AC	12 ms	13 MB
g++	random_01	AC	12 ms	13 MB
g++	random_02	AC	5 ms	5 MB
g++	random_03	AC	11 ms	13 MB
g++	random_04	AC	11 ms	13 MB
g++	random_ab_00	AC	12 ms	13 MB
g++	random_ab_01	AC	13 ms	13 MB
g++	random_ab_02	AC	5 ms	5 MB
g++	random_ab_03	AC	11 ms	13 MB
g++	random_ab_04	AC	11 ms	13 MB

Back to top page