syakyo-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Luzhiled/syakyo-library

:heavy_check_mark: src/string/wildcard-pattern-matching.hpp

Depends on

Verified with

Code

#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
Back to top page