noshi91のメモ (original) (raw)

この広告は、90日以上更新していないブログに表示しています。

問題

文字集合を $\Sigma := \lbrace 0, 1, \dots, \sigma \rbrace$ とする文字列 $S$ と $T$ がある。 $S$ の長さ $\lvert T \rvert$ の連続部分列のそれぞれについて、 $T$ にマッチするか判定せよ。ただし文字列がマッチするとは、それぞれの文字列中の $0$ を好きな文字に置き換えたときに両文字列が一致することを指す。

解法 (Clifford & Clifford, 2007 [1])

文字列 $X$ と $Y$ がマッチすることと $\sum _ i X _ i Y _ i (X _ i - Y _ i) ^ 2 = 0$ が同値である。したがって、各 $k$ について $\sum _ i S _ {k + i} T _ i (S _ {k + i} - T _ i) ^ 2$ を計算できればよい。これは括弧を展開して積和形にし、それぞれの項については適切な列を FFT を用いて畳み込めばよい。時間計算量は $O ( \lvert S \rvert \log \lvert S \rvert)$ 。

値域の削減 (Clifford, Efremenko, Porat, & Rothschild, 2009 [2])

前述した解法は最終的に $0$ か判定したい値が $\lvert S \rvert \sigma ^ 4$ 程度まで大きくなり得る。

\begin{align} S ' _ i := \begin{cases} 0 \quad & ( S _ i = 0 ) \cr 1 \quad & ( S _ i \neq 0 ) \end{cases} \cr T ' _ i := \begin{cases} 0 \quad & ( T _ i = 0 ) \cr 1 \quad & ( T _ i \neq 0 ) \end{cases} \end{align}

と定義すれば、 $\sum _ i S ' _ {k + i} T ' _ i (S _ {k + i} - T _ i) ^ 2 = 0$ で判定しても問題ない。これで $\lvert S \rvert \sigma ^ 2$ まで削減された。ちなみに $\lvert S \rvert = 1.4 \times 10 ^ 6, \sigma = 26$ とするとこの値は $998244353$ 以下になる。

乱択

素数 $P \geq \sigma$ と一様乱数 $r _ i$ を用いて、 $\sum _ i r _ i S ' _ {k + i} T ' _ i (S _ {k + i} - T _ i) = 0 \pmod P$ を判定してもよい。このとき $S$ の各連続部分列について、マッチしていると誤って判定される確率は $1 / P$ 以下である。 $\sigma$ が大きくても値域の問題が発生しないことと、項を展開すると $2$ つしかないため畳み込みの回数が減るという利点がある。

巡回畳み込みを用いた高速化

これらのアルゴリズム内では、 $\sum _ i A _ {k + i} B _ i$ を各 $k$ について求めるために畳み込みを用いる。これは $B$ を反転して通常の畳み込みを行えばよいのだが、畳み込んだ結果のうち先頭 $\lvert B \rvert - 1$ 項と末尾 $\lvert B \rvert - 1$ 項は必要がない。よって巡回畳み込みでこれらの部分が重なっても問題なく、畳み込みの長さを短くすることができる。

線形性を用いた高速化

アルゴリズム中では $2, 3$ 回の畳み込みを行い、その和だけに興味がある。よってそれぞれの畳み込みにおいて IDFT を行わず、全部足し合わせて最後に $1$ 度だけ IDFT を行うことで定数倍高速化になる。ボトルネックには関係ないと思われるが、IDFT の後の規格化も非零判定だけなので必要ない。

ワイルドカードが一方のみにある場合の高速化

$S$ 側にワイルドカードがない場合、常に $S ' _ i = 1$ である。すると $\sum _ i S ' _ {k + i} T ' _ i (S _ {k + i} - T _ i) ^ 2 = 0$ を積和形にした際に現れる $3$ つの項の内 $1$ つは $k$ に依存しない値になり、その総和は定数となる。 $T$ 側にワイルドカードがない場合も同様の議論により、累積和で $1$ つの項は計算できる。前述した乱択の場合も、 $2$ つの畳み込みが $1$ つに削減される。

$\lvert S \rvert \gg \lvert T \rvert$ の場合の高速化

判定するべき連続部分列のうち最初の $\lvert T \rvert$ 個を判定するためには $S$ の先頭 $2 \lvert T \rvert - 1$ 文字があれば十分であり、これを切り出して今までのアルゴリズムを適用すれば $O ( \lvert T \rvert \log \lvert T \rvert)$ で判定できる。この調子で $\lvert T \rvert$ 個ずつ判定すると全体で $O ( \lvert S \rvert \log \lvert T \rvert)$ となる。一度に判定する量は $\lvert T \rvert$ の何倍かの範囲で調整した方が定数倍が良いかもしれない。

実装例

乱択ベース、巡回畳み込みと線形性の高速化あり

https://judge.yosupo.jp/submission/211249

参考文献

[1] Clifford, P., & Clifford, R. (2007). Simple deterministic wildcard matching. Information Processing Letters, 101(2), 53-54.

[2] Clifford, R., Efremenko, K., Porat, E., & Rothschild, A. (2009, January). From coding theory to efficient pattern matching. In Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 778-784). Society for Industrial and Applied Mathematics.