This documentation is automatically generated by online-judge-tools/verification-helper
// verification-helper: PROBLEM https://atcoder.jp/contests/abc307/tasks/abc307_h
// verification-helper: PROBLEM https://atcoder.jp/contests/abc307/tasks/abc307_ex
#include "src/cpp-template/header/size-alias.hpp"
#include "src/math/modular-arithmetic/static-modint.hpp"
#include "src/string/wildcard-pattern-matching.hpp"
#include <algorithm>
#include <iostream>
namespace luz {
void main_() {
const i64 mod = 998244353;
usize l, w;
std::string s;
std::cin >> l >> w >> s;
s += std::string(w - 1, '.');
s += s.substr(0, w - 1);
std::string p;
std::cin >> p;
auto wpm = wildcard_pattern_matching(s.begin(), s.end(), p.begin(), p.end(), '_', mod);
std::cout << std::count(wpm.begin(), wpm.end(), 1) << std::endl;
}
} // namespace luz
int main() {
luz::main_();
}
#line 1 "test/atcoder/abc307_h.test.cpp"
// verification-helper: PROBLEM https://atcoder.jp/contests/abc307/tasks/abc307_h
// verification-helper: PROBLEM https://atcoder.jp/contests/abc307/tasks/abc307_ex
#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/modular-arithmetic/static-modint.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 4 "src/math/modular-arithmetic/static-modint.hpp"
#include <cassert>
#include <iostream>
namespace luz {
template < u32 mod >
class StaticPrimeModInt {
using modint = StaticPrimeModInt;
u32 v;
public:
StaticPrimeModInt(): v(0) {}
template < typename T >
StaticPrimeModInt(T t) {
i64 x = (i64)(t % (i64)mod);
if (x < 0) x += mod;
v = (u32)x;
}
u32 val() const {
return v;
}
modint &operator+=(const modint &rhs) {
v += rhs.v;
if (v >= mod) v -= mod;
return *this;
}
modint &operator-=(const modint &rhs) {
v += mod - rhs.v; // <-
if (v >= mod) v -= mod;
return *this;
}
modint &operator*=(const modint &rhs) {
v = (u32)(u64(1) * v * rhs.v % mod);
return *this;
}
modint &operator/=(const modint &rhs) {
*this *= rhs.inverse();
return *this;
}
modint operator+() const {
return *this;
}
modint operator-() const {
return modint() - *this;
}
friend modint operator+(const modint &lhs, const modint &rhs) {
return modint(lhs) += rhs;
}
friend modint operator-(const modint &lhs, const modint &rhs) {
return modint(lhs) -= rhs;
}
friend modint operator*(const modint &lhs, const modint &rhs) {
return modint(lhs) *= rhs;
}
friend modint operator/(const modint &lhs, const modint &rhs) {
return modint(lhs) /= rhs;
}
friend bool operator==(const modint &lhs, const modint &rhs) {
return lhs.v == rhs.v;
}
friend bool operator!=(const modint &lhs, const modint &rhs) {
return lhs.v != rhs.v;
}
modint pow(i64 n) const {
assert(0 <= n);
modint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
modint inverse() const {
assert(v != 0);
return pow(mod - 2);
}
static constexpr u32 get_mod() {
return mod;
}
friend std::ostream &operator<<(std::ostream &os,
const modint &m) {
os << m.val();
return os;
}
};
using modint998244353 = StaticPrimeModInt< 998244353 >;
using modint1000000007 = StaticPrimeModInt< 1000000007 >;
} // namespace luz
#line 2 "src/string/wildcard-pattern-matching.hpp"
#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"
#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
#line 7 "test/atcoder/abc307_h.test.cpp"
#include <algorithm>
#line 10 "test/atcoder/abc307_h.test.cpp"
namespace luz {
void main_() {
const i64 mod = 998244353;
usize l, w;
std::string s;
std::cin >> l >> w >> s;
s += std::string(w - 1, '.');
s += s.substr(0, w - 1);
std::string p;
std::cin >> p;
auto wpm = wildcard_pattern_matching(s.begin(), s.end(), p.begin(), p.end(), '_', mod);
std::cout << std::count(wpm.begin(), wpm.end(), 1) << std::endl;
}
} // namespace luz
int main() {
luz::main_();
}