This documentation is automatically generated by online-judge-tools/verification-helper
#include "src/string/wildcard-pattern-matching.hpp"
#pragma once
#include "src/cpp-template/header/int-alias.hpp"
#include "src/cpp-template/header/size-alias.hpp"
#include "src/math/convolution/modint-convolution.hpp"
#include <cassert>
#include <vector>
namespace luz {
// [warning] false positive occur expect O(1/M)
// when values are randomized
// [note] try to use multiple mods if necessary
// [note] all of values are needed \in [1, mod)
template < class Iter >
std::vector< i32 > wildcard_pattern_matching(Iter f1, Iter l1,
Iter f2, Iter l2,
const i64 wildcard,
i64 mod) {
usize n = l1 - f1, m = l2 - f2;
assert(m <= n);
std::vector< i64 > as(n), bs(n), cs(n), ss(m), ts(m), us(m);
for (Iter iter = f1; iter != l1; ++iter) {
i64 x(*iter == wildcard ? 0 : *iter);
i64 y(*iter == wildcard ? 0 : 1);
usize i = iter - f1;
as[i] = y * x * x % mod;
bs[i] = y * x * (mod - 2) % mod;
cs[i] = y;
}
for (Iter iter = f2; iter != l2; ++iter) {
i64 x(*iter == wildcard ? 0 : *iter);
i64 y(*iter == wildcard ? 0 : 1);
usize i = l2 - iter - 1;
ss[i] = y;
ts[i] = y * x;
us[i] = y * x * x % mod;
}
auto f = modint_convolution(as, ss, mod);
auto g = modint_convolution(bs, ts, mod);
auto h = modint_convolution(cs, us, mod);
std::vector< i32 > result(n - m + 1);
for (usize i = 0; i < result.size(); i++) {
usize j = i + m - 1;
i64 x((f[j] + g[j] + h[j]) % mod);
if (x == 0) result[i] = 1;
}
return result;
}
} // namespace luz
#line 2 "src/string/wildcard-pattern-matching.hpp"
#line 2 "src/cpp-template/header/int-alias.hpp"
#include <cstdint>
namespace luz {
using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
}
#line 2 "src/cpp-template/header/size-alias.hpp"
#include <cstddef>
namespace luz {
using isize = std::ptrdiff_t;
using usize = std::size_t;
}
#line 2 "src/math/convolution/modint-convolution.hpp"
#line 2 "src/math/modular-arithmetic/mod-pow.hpp"
#line 4 "src/math/modular-arithmetic/mod-pow.hpp"
namespace luz {
i64 mod_pow(i64 b, i64 e, i64 mod) {
if (mod == 1) return 0;
i64 ans{1};
while (e) {
if (e & 1) {
ans = ans * b % mod;
}
b = b * b % mod;
e /= 2;
}
return ans;
}
}
#line 6 "src/math/convolution/modint-convolution.hpp"
#include <vector>
namespace luz {
usize bw(u64 x) {
if (x == 0) return 0;
return 64 - __builtin_clzll(x);
}
void butterfly(std::vector< i64 > &vs, i64 mod) {
constexpr i64 root = 62;
usize n = vs.size(), h = bw(n) - 1;
static std::vector< i64 > rt(2, 1);
for (static usize k = 2, s = 2; k < n; k *= 2, s++) {
rt.resize(n);
i64 z[] = {1, mod_pow(root, mod >> s, mod)};
for (usize i = k; i < 2 * k; i++) {
rt[i] = rt[i / 2] * z[i & 1] % mod;
}
}
std::vector< i64 > rev(n);
for (usize i = 0; i < n; i++) {
rev[i] = (rev[i / 2] | (i & 1) << h) / 2;
}
for (usize i = 0; i < n; i++) {
if ((i64)i >= rev[i]) continue;
std::swap(vs[i], vs[rev[i]]);
}
for (usize k = 1; k < n; k *= 2) {
for (usize i = 0; i < n; i += 2 * k) {
for (usize j = 0; j < k; j++) {
i64 z = rt[j + k] * vs[i + j + k] % mod;
i64 &vi = vs[i + j];
vs[i + j + k] = vi - z + (z > vi ? mod : 0);
vi += (vi + z >= mod ? z - mod : z);
}
}
}
}
std::vector< i64 > modint_convolution(std::vector< i64 > f,
std::vector< i64 > g,
i64 mod) {
usize n = f.size(), m = g.size();
if (not n or not m) return {};
usize s = 1 << bw(n + m - 2);
i64 inv = mod_pow(s, mod - 2, mod);
f.resize(s);
g.resize(s);
butterfly(f, mod);
butterfly(g, mod);
std::vector< i64 > res(s);
for (isize i = 0; (usize)i < s; i++) {
res[-i & (s - 1)] = f[i] * g[i] % mod * inv % mod;
}
butterfly(res, mod);
res.resize(n + m - 1);
return res;
}
}
#line 6 "src/string/wildcard-pattern-matching.hpp"
#include <cassert>
#line 9 "src/string/wildcard-pattern-matching.hpp"
namespace luz {
// [warning] false positive occur expect O(1/M)
// when values are randomized
// [note] try to use multiple mods if necessary
// [note] all of values are needed \in [1, mod)
template < class Iter >
std::vector< i32 > wildcard_pattern_matching(Iter f1, Iter l1,
Iter f2, Iter l2,
const i64 wildcard,
i64 mod) {
usize n = l1 - f1, m = l2 - f2;
assert(m <= n);
std::vector< i64 > as(n), bs(n), cs(n), ss(m), ts(m), us(m);
for (Iter iter = f1; iter != l1; ++iter) {
i64 x(*iter == wildcard ? 0 : *iter);
i64 y(*iter == wildcard ? 0 : 1);
usize i = iter - f1;
as[i] = y * x * x % mod;
bs[i] = y * x * (mod - 2) % mod;
cs[i] = y;
}
for (Iter iter = f2; iter != l2; ++iter) {
i64 x(*iter == wildcard ? 0 : *iter);
i64 y(*iter == wildcard ? 0 : 1);
usize i = l2 - iter - 1;
ss[i] = y;
ts[i] = y * x;
us[i] = y * x * x % mod;
}
auto f = modint_convolution(as, ss, mod);
auto g = modint_convolution(bs, ts, mod);
auto h = modint_convolution(cs, us, mod);
std::vector< i32 > result(n - m + 1);
for (usize i = 0; i < result.size(); i++) {
usize j = i + m - 1;
i64 x((f[j] + g[j] + h[j]) % mod);
if (x == 0) result[i] = 1;
}
return result;
}
} // namespace luz