indexは \(0\) から始まるとし、文字列 \(S,T\) を \(01\) 数列と同一視する。 また、文字列 \(S\) の長さを \(|S|\)、\(i\) 文字目を \(S[i]\) とそれぞれ表す。文字列 \(S\) の \(i\) 文字目からの連続する \(|T|\) 文字からなる部分文字列を \(S_i\) とおく。

求めるべきは \(\min_i \{ S_i \text{ と } T \text{ で異なっている文字数} \}\) だが、これはかわりに \(\max_i\{ S_i \text{ と } T \text{ で一致している文字数}\}\) を求め、\(|T|\) から引けば求まる。後者で考える。

各 \(i\) について \(S_i\) と \(T\) で一致している文字数が求まれば良い。文字の種類ごとに分けて考えることで、これは 「\(T[k]=0\) かつ \(S[i+k]=0\) である \(k\) の個数」＋「\(T[k]=1\) かつ \(S[i+k]=1\) である \(k\) の個数」に等しいことがわかる。こうして分解された2つの問題は、\(0,1\) が入れ替わっただけの同じ問題であるため、一方が解ければ他方も同様に解ける。後者について考える。

\(S,T\) は \(01\) 数列であるため、「\(T[k]=1\) かつ \(S[i+k]=1\) である \(k\) の個数」は \(\sum_k T[k]*S[i+k]\) に等しい。したがって、これを全ての \(i\) について高速に求めれば良い。

\(T\) を reverse するとこの式は\(\sum_k T[|T|-1-k]*S[i+k] = \sum_{p+q=|T|-1+i} T[p]*S[q]\) となるため FFT を用いることで全ての \(i\) についてを \(O(|S| \log |S|)\) で求めることができる。以上により元の問題が解けた。

実装例(C++)

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

using Modint=modint998244353;
void chmax(int& a, int b){if(a<b)a=b;}

int main(){
    string S, T;
    cin >> S >> T;
    reverse(T.begin(), T.end());
    const int slen=S.size(), tlen=T.size();
    vector<Modint> s0(slen), s1(slen), t0(tlen), t1(tlen);
    for(int i=0;i<slen;i++)(S[i]=='0'?s0:s1)[i]=1;
    for(int i=0;i<tlen;i++)(T[i]=='0'?t0:t1)[i]=1;
    vector<Modint> st0=convolution(s0, t0);
    vector<Modint> st1=convolution(s1, t1);
    int ans=0;
    for(int i=tlen-1;i<slen;i++) chmax(ans, st0[i].val() + st1[i].val());
    cout << tlen-ans << endl;
}