この問題は、\(S\) から長さ \(|T|\) の部分文字列を取り出したときの \(T\) とのハミング距離を最小化する問題と見ることができます。
すなわち、\(s_i\) を \(S\) の \(i\) 文字目、\(t_i\) を \(T\) の \(i\) 文字目、\(\oplus\) を XOR の演算子として、 \(\displaystyle \min_{0 ≤ i ≤ |S| - |T|} \sum_{j=1}^{|T|}(s_{i + j} \oplus t_j)\) が答えになります。

\(\displaystyle \sum_{j=1}^{|T|}(s_{i + j} \oplus t_j)\) を全ての \(i\) について求めることを考えてみましょう。
愚直に求めると計算量が \(\Theta(|S||T|)\) になり TLE してしまいますが、式が畳み込みのような形になっていることに注目し、\(T\) を左右反転して \(\displaystyle \sum_{j=1}^{|T|}(s_{i + j} \oplus t_{|T|-1-j})\) とします。

以下 \(T\) は左右反転しておくものとします。
\(S\) と \(T\) の以下の式により畳み込んだものを \(C = (c_2, c_3, \dots, c_{|S|+|T|})\) とすると、

\[ c_i = \sum_{i=j+k}s_j \oplus t_k \]

です。ここで、\(c_{i+|T|-1} = \displaystyle \sum_{j=1}^{|T|}(s_{i + j} \oplus t_{|T|-1-j})\) であるので、この畳み込みを高速に求めればこの問題を解くことができます。
畳み込みの XOR の部分が掛け算であれば高速フーリエ変換による畳み込みが使えるので、XOR を掛け算に分解します。

\[ c_i = \sum_{i=j+k}s_j(1 - t_k) + \sum_{i=j+k}(1 - s_j)t_k \]

これで、高速フーリエ変換を利用して \(C\) を \(O((|S| + |T|) \log(|S| + |T|))\) で求められるので、この問題を解くことができました。

実装には AC-Library の convolution を利用できます。

回答例 (C++)

#include <iostream>
#include <vector>
#include <atcoder/convolution>
#include <atcoder/modint>
using namespace std;
using Modint = atcoder::modint998244353;
const int INF = numeric_limits<int>::max() / 2;
void chmin(int& a, int b){ if(a > b) a = b; }

int main(){
    string S, T;
    cin >> S >> T;
    reverse(T.begin(), T.end());
    const int N = S.size(), M = T.size();
    vector<Modint> s1(N), s2(N), t1(N), t2(N);
    for(int i = 0; i < N; i++) (S[i] == '0' ? s1 : s2)[i] = 1;
    for(int i = 0; i < M; i++) (T[i] == '0' ? t1 : t2)[i] = 1;
    s1 = atcoder::convolution(s1, t2);
    s2 = atcoder::convolution(s2, t1);
    int ans = INF;
    for(int i = M - 1; i < N; i++) chmin(ans, s1[i].val() + s2[i].val());
    cout << ans << endl;
}

回答例 (Python)

import numpy as np

S = input()
T = input()
N = len(S)
M = len(T)

S1 = np.array(list(map(int, S)))
S2 = 1 - S1
T1 = np.array(list(map(int, reversed(T))))
T2 = 1 - T1

def conv(f, g):
    siz = len(f) + len(g) - 1
    siz = 1 << (siz - 1).bit_length()
    f = np.fft.rfft(f, siz)
    g = np.fft.rfft(g, siz)
    f *= g
    f = np.fft.irfft(f, siz)
    return np.rint(f).astype(np.int32)

A = conv(S1, T2) + conv(S2, T1)
print(np.min(A[M - 1 : N]))