問題 文字集合を とする文字列 と がある。 の長さ の連続部分列のそれぞれについて、 にマッチするか判定せよ。 ただし文字列がマッチするとは、それぞれの文字列中の を好きな文字に置き換えたときに両文字列が一致することを指す。 解法 (Clifford & Clifford, 2007 [1]) 文字列 と がマッチすることと が同値である。 したがって、各 について を計算できればよい。 これは括弧を展開して積和形にし、それぞれの項については適切な列を FFT を用いて畳み込めばよい。 時間計算量は 。 値域の削減 (Clifford, Efremenko, Porat, & Rothsch…