ABC196-F Substring 2 解説
シンプルながら FFT への帰着がきれいで、良い問題だと思う。
解説
ビット文字列 $T$ を $S$ の部分文字列とするには、最小何ビット反転させればよいかを求める問題。
単なる文字列検索なら KMP 法を使ったりすればよいが、今回はビットの反転数を求めるので、前計算を利用して時間を削っていくタイプの文字列アルゴリズムは使えない。
また、制約が $10^5$ くらいなら std::bitset で高速化できるが、今回はもっと制約が大きいので、それも使えない。
$S$ の上で $T$ を動かしていく様子をイメージすると畳み込みっぽいのでそれを考えると、$S[i\cdots]$ と $T$ を重ねているとき、添字は $S[i+k]$ と $T[k]$ で対応する。そこで、$T$ を反転させて、$S[i+k]$ と $T[-k]$ が対応するような状態にしてやれば、多項式の畳み込みに帰着できる。$\mathrm{xor}$ を乗算に帰着することはできないが、$0,1$ の代わりに $-1,1$ を割り当てると、畳み込まれる項数が結果の一項あたり $|T|$ と同じことにより、$\mathrm{xor}$ が $1$ となる個数を求められる。
