Wildcard Pattern Matching
(src/string/wildcard_pattern_matching.hpp)

• View this file on GitHub
• Last update: 2024-05-26 15:33:49+09:00
• Include: #include "src/string/wildcard_pattern_matching.hpp"

入力

文字列 $S, T\ (\vert S \vert \geq \vert T \vert)$

出力

長さの等しい文字列 $S ^ \prime, T ^ \prime$ が各 $0 \leq i < \vert S ^ \prime \vert $ について

• $S ^ \prime _ i = T ^ \prime _ i$
• $S ^ \prime _ i$ が wildcard
• $T ^ \prime _ i$ が wildcard

のいずれかを満たすとき，$S ^ \prime$ と $T ^ \prime$ はマッチすると呼ぶことにする．

このときの

\[v_i = \begin{cases} 1 & \text{($S \lbrack i, i + \vert T \vert)$ と $T$ がマッチしている)} \\ 0 & \text{(otherwise)} \end{cases} \quad (0 \leq i \leq \vert S \vert - \vert T \vert)\]

で定まる長さ $\vert S \vert - \vert T \vert + 1$ の配列 $v$

計算量

• 時間計算量 $\mathrm{O}((\vert S \vert + \vert T \vert) \log (\vert S \vert + \vert T \vert))$
• 空間計算量 $\mathrm{O}(\vert S \vert + \vert T \vert)$

概要

決定的解法

任意の文字 $s, t$ について

\[\mathrm{cmp}(s, t) := (s - t)^2 \mathbf{1}(s \gt 0) \mathbf{1}(t \gt 0)\]

と定めると，$\mathrm{cmp}(s, t)$ は $s = t$ もしくは $s, t$ の少なくとも一方が wildcard に一致するときにのみ $0$ となり，それ以外の場合は正の値を取る． ただし，$\mathbf{1}(x)$ は命題 $x$ が真のとき $1$，偽のとき $0$ を返す関数とする．

従って，

\[\begin{aligned} S \lbrack i, i + \vert T \vert) = T && \iff & \sum _ {k = 0} ^ {\vert T \vert - 1} \mathrm{cmp}(S \lbrack i + k \rbrack, T \lbrack k \rbrack) = 0 \\ && \iff & \sum _ {k = 0} ^ {\vert T \vert - 1} \left \lbrack S \lbrack i + k \rbrack^2 \mathbf{1}(S \lbrack i + k \rbrack \gt 0) \mathbf{1}(T \lbrack k \rbrack \gt 0) \right. \\ &&& - 2 S \lbrack i + k \rbrack T \lbrack k \rbrack \mathbf{1}(S \lbrack i + k \rbrack \gt 0) \mathbf{1}(T \lbrack k \rbrack \gt 0) \\ &&& \left. + T \lbrack k \rbrack^2 \mathbf{1}(S \lbrack i + k \rbrack \gt 0) \mathbf{1}(T \lbrack k \rbrack \gt 0) \right \rbrack = 0 \end{aligned}\]

が成立し，最後の式は畳み込みにより計算可能である．

また，現れる文字の種類数を $\sigma$ として，畳み込んだ結果現れる数値の最大値 $\sigma ^ 2 \vert T\vert$ が畳み込みで用いる $\text{mod}$ 未満ならば判定は決定的となる．

乱択解法

素数 $P \geq \sigma$ 及び $0$ 以上 $P$ 未満の一様乱数 $r _ k\ (k = 0, \dots , \vert T \vert - 1)$ を取る． マッチの判定式を

\[\sum _ {k = 0} ^ {\vert T \vert - 1} r _ k (S \lbrack i + k \rbrack - T \lbrack k \rbrack) \mathbf{1}(S \lbrack i + k \rbrack \gt 0) \mathbf{1}(T \lbrack k \rbrack \gt 0) \equiv 0 \pmod{P}\]

と改めると，Schwartz-Zippel の補題よりこの判定式によりマッチしていないのにマッチしていると誤って判定される確率は $1 / P$ 以下となる．

出題例

• AtCoder Beginner Contest 307 Ex - Marquee
• DEGwer さんの D 論応援コンテスト H - Incomplete Notes
• Codeforces Round 947 (Div. 1 + Div. 2) G. Zimpha Fan Club

Links

• ワイルドカードマッチングの高速化 - noshi91のメモ

Verified with

• test/yosupo/wildcard_pattern_matching.test.cpp

Code

#include <string>
#include "../atcoder/convolution"

std::vector<bool> wildcard_pattern_matching(const std::string& s, const std::string& t, char wild = '?') {
    int n = s.size(), m = t.size();
    assert(n >= m and n > 0);
    char mini = s[0];
    for (const auto& c : s) {
        if (c != wild) {
            mini = std::min(mini, c);
        }
    }
    for (const auto& c : t) {
        if (c != wild) {
            mini = std::min(mini, c);
        }
    }
    std::vector<atcoder::modint998244353> f1(n), f2(n), f3(n), g1(m), g2(m), g3(m);
    for (int i = 0; i < n; i++) {
        atcoder::modint998244353 x = (s[i] == wild ? 0 : s[i] - mini + 1), y = (s[i] == wild ? 0 : 1);
        f1[i] = y;
        f2[i] = y * x;
        f3[i] = y * x * x;
    }
    for (int i = 0; i < m; i++) {
        atcoder::modint998244353 x = (t[i] == wild ? 0 : t[i] - mini + 1), y = (t[i] == wild ? 0 : 1);
        g1[m - 1 - i] = y;
        g2[m - 1 - i] = y * x;
        g3[m - 1 - i] = y * x * x;
    }
    auto h1 = atcoder::convolution(f1, g3);
    auto h2 = atcoder::convolution(f2, g2);
    auto h3 = atcoder::convolution(f3, g1);
    std::vector<bool> res(n - m + 1);
    for (int i = 0; i < n - m + 1; i++) {
        res[i] = (h1[m - 1 + i] - 2 * h2[m - 1 + i] + h3[m - 1 + i] == 0);
    }
    return res;
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
    ~~~~~~~~~~~~~~^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
    ~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
                ~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: atcoder/convolution.hpp: line -1: no such header

Back to top page