This problem is equivalent to the problem that asks to find the minimum hamming distance between \(T\) and a substring of \(S\) of length \(|T|\).
Accordingly, the answer is \(\displaystyle \min_{0 ≤ i ≤ |S| - |T|} \sum_{j=1}^{|T|}(s_{i + j} \oplus t_j)\), where \(s_i\) denotes the \(i\)-th letter of \(S\), \(t_i\) is the \(i\)-th letter of \(T\), and \(\oplus\) is the XOR operator.

Let us consider calculating \(\displaystyle \sum_{j=1}^{|T|}(s_{i + j} \oplus t_j)\) for all \(i\).
With a naive way, the time complexity will be \(\Theta(|S||T|)\), which will lead to TLE. Observe that the expression looks like a convolution. By reversing \(T\), we have \(\displaystyle \sum_{j=1}^{|T|}(s_{i + j} \oplus t_{|T|-1-j})\).

Hereinafter we assume that \(T\) is reversed.
Let \(C = (c_2, c_3, \dots, c_{|S|+|T|})\) be the convolution of \(S\) and \(T\) by the equation:

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

then \(c_{i+|T|-1} = \displaystyle \sum_{j=1}^{|T|}(s_{i + j} \oplus t_{|T|-1-j})\), so it is sufficient to find this convolution.

If there is multiplication instead of XOR, we can apply Fast Fourier Transform (FFT) to find the convolution, so let us decompose XOR to multiplications.

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

FFT enables to find \(C\) in a total of \(O((|S| + |T|) \log(|S| + |T|))\), so the problem has been solved.

For implementation, we can use convolution in AC-Library.

Sample Code (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;
}

Sample Code (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]))