description: The Winter holiday will be here soon. Mr. Chanek wants to decorate his house's wall with ornaments. The wall can be represented as a binary string a of length n. His favorite nephew has another binary string b of length m (m ≤ n).
  
  Mr. Chanek's nephew loves the non-negative integer k. His nephew wants exactly k occurrences of b as substrings in a. 
  
  However, Mr. Chanek does not know the value of k. So, for each k (0 ≤ k ≤ n - m + 1), find the minimum number of elements in a that have to be changed such that there are exactly k occurrences of b in a.
  
  A string s occurs exactly k times in t if there are exactly k different pairs (p,q) such that we can obtain s by deleting p characters from the beginning and q characters from the end of t.
  
  Input
  
  The first line contains two integers n and m (1 ≤ m ≤ n ≤ 500) — size of the binary string a and b respectively.
  
  The second line contains a binary string a of length n.
  
  The third line contains a binary string b of length m.
  
  Output
  
  Output n - m + 2 integers — the (k+1)-th integer denotes the minimal number of elements in a that have to be changed so there are exactly k occurrences of b as a substring in a.
  
  Example
  
  Input
  
  
  9 3
  100101011
  101
  
  
  Output
  
  
  1 1 0 1 6 -1 -1 -1
  
  Note
  
  For k = 0, to make the string a have no occurrence of 101, you can do one character change as follows.
  
  100101011 → 100100011
  
  For k = 1, you can also change a single character.
  
  100101011 → 100001011
  
  For k = 2, no changes are needed.
solution: #include <bits/stdc++.h>
  using namespace std;
  template <typename T, int NDIMS>
  struct tensor_view {
    static_assert(NDIMS >= 0, "NDIMS must be nonnegative");
  
   protected:
    std::array<int, NDIMS> shape;
    std::array<int, NDIMS> strides;
    T* data;
    tensor_view(std::array<int, NDIMS> shape_, std::array<int, NDIMS> strides_,
                T* data_)
        : shape(shape_), strides(strides_), data(data_) {}
  
   public:
    tensor_view() : shape{0}, strides{0}, data(nullptr) {}
  
   protected:
    int flatten_index(std::array<int, NDIMS> idx) const {
      int res = 0;
      for (int i = 0; i < NDIMS; i++) {
        res += idx[i] * strides[i];
      }
      return res;
    }
    int flatten_index_checked(std::array<int, NDIMS> idx) const {
      int res = 0;
      for (int i = 0; i < NDIMS; i++) {
        assert(0 <= idx[i] && idx[i] < shape[i]);
        res += idx[i] * strides[i];
      }
      return res;
    }
  
   public:
    T& operator[](std::array<int, NDIMS> idx) const {
      return data[flatten_index(idx)];
    }
    T& at(std::array<int, NDIMS> idx) const {
      return data[flatten_index_checked(idx)];
    }
    template <int D = NDIMS>
    typename std::enable_if<(0 < D), tensor_view<T, NDIMS - 1>>::type operator[](
        int idx) const {
      std::array<int, NDIMS - 1> nshape;
      std::copy(shape.begin() + 1, shape.end(), nshape.begin());
      std::array<int, NDIMS - 1> nstrides;
      std::copy(strides.begin() + 1, strides.end(), nstrides.begin());
      T* ndata = data + (strides[0] * idx);
      return tensor_view<T, NDIMS - 1>(nshape, nstrides, ndata);
    }
    template <int D = NDIMS>
    typename std::enable_if<(0 < D), tensor_view<T, NDIMS - 1>>::type at(
        int idx) const {
      assert(0 <= idx && idx < shape[0]);
      return operator[](idx);
    }
    template <int D = NDIMS>
    typename std::enable_if<(0 == D), T&>::type operator*() const {
      return *data;
    }
    template <typename U, int D>
    friend struct tensor_view;
    template <typename U, int D>
    friend struct tensor;
  };
  template <typename T, int NDIMS>
  struct tensor {
    static_assert(NDIMS >= 0, "NDIMS must be nonnegative");
  
   protected:
    std::array<int, NDIMS> shape;
    std::array<int, NDIMS> strides;
    int len;
    T* data;
  
   public:
    tensor() : shape{0}, strides{0}, len(0), data(nullptr) {}
    explicit tensor(std::array<int, NDIMS> shape_, const T& t = T()) {
      shape = shape_;
      strides[NDIMS - 1] = 1;
      for (int i = NDIMS - 1; i > 0; i--) {
        strides[i - 1] = strides[i] * shape[i];
      }
      len = strides[0] * shape[0];
      data = new T[len];
      std::fill(data, data + len, t);
    }
    tensor(const tensor& o)
        : shape(o.shape), strides(o.strides), len(o.len), data(new T[len]) {
      for (int i = 0; i < len; i++) {
        data[i] = o.data[i];
      }
    }
    tensor& operator=(tensor&& o) noexcept {
      using std::swap;
      swap(shape, o.shape);
      swap(strides, o.strides);
      swap(len, o.len);
      swap(data, o.data);
      return *this;
    }
    tensor(tensor&& o) : tensor() { *this = std::move(o); }
    tensor& operator=(const tensor& o) { return *this = tensor(o); }
    ~tensor() { delete[] data; }
    using view_t = tensor_view<T, NDIMS>;
    view_t view() { return tensor_view<T, NDIMS>(shape, strides, data); }
    operator view_t() { return view(); }
    using const_view_t = tensor_view<const T, NDIMS>;
    const_view_t view() const {
      return tensor_view<const T, NDIMS>(shape, strides, data);
    }
    operator const_view_t() const { return view(); }
    T& operator[](std::array<int, NDIMS> idx) { return view()[idx]; }
    T& at(std::array<int, NDIMS> idx) { return view().at(idx); }
    const T& operator[](std::array<int, NDIMS> idx) const { return view()[idx]; }
    const T& at(std::array<int, NDIMS> idx) const { return view().at(idx); }
    template <int D = NDIMS>
    typename std::enable_if<(0 < D), tensor_view<T, NDIMS - 1>>::type operator[](
        int idx) {
      return view()[idx];
    }
    template <int D = NDIMS>
    typename std::enable_if<(0 < D), tensor_view<T, NDIMS - 1>>::type at(
        int idx) {
      return view().at(idx);
    }
    template <int D = NDIMS>
    typename std::enable_if<(0 < D), tensor_view<const T, NDIMS - 1>>::type
    operator[](int idx) const {
      return view()[idx];
    }
    template <int D = NDIMS>
    typename std::enable_if<(0 < D), tensor_view<const T, NDIMS - 1>>::type at(
        int idx) const {
      return view().at(idx);
    }
    template <int D = NDIMS>
    typename std::enable_if<(0 == D), T&>::type operator*() {
      return *view();
    }
    template <int D = NDIMS>
    typename std::enable_if<(0 == D), const T&>::type operator*() const {
      return *view();
    }
  };
  vector<int> prefix_func(string s) {
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
      int j = pi[i - 1];
      while (j > 0 && s[i] != s[j]) j = pi[j - 1];
      if (s[i] == s[j]) j++;
      pi[i] = j;
    }
    return pi;
  }
  vector<int> kmp(const string& s, const string& pat) {
    vector<int> p = prefix_func(pat + '\0' + s), res;
    for (int i = (int)p.size() - (int)s.size(); i < p.size(); i++)
      if (p[i] == pat.size()) res.push_back(i - 2 * pat.size());
    return res;
  }
  void compute_automaton(string s, vector<vector<int>>& aut) {
    s += '#';
    int n = s.size();
    vector<int> pi = prefix_func(s);
    aut.assign(n, vector<int>(2));
    for (int i = 0; i < n; i++) {
      for (int c = 0; c < 2; c++) {
        if (i > 0 && '0' + c != s[i])
          aut[i][c] = aut[pi[i - 1]][c];
        else
          aut[i][c] = i + ('0' + c == s[i]);
      }
    }
  }
  int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    string a, b;
    cin >> a >> b;
    vector<vector<int>> aut;
    compute_automaton(b, aut);
    const int INF = 1e9;
    tensor<int, 2> dp({m + 1, n - m + 2}, INF);
    dp[{0, 0}] = 0;
    for (int i = 0; i < n; i++) {
      tensor<int, 2> ndp({m + 1, n - m + 2}, INF);
      for (int pi = 0; pi <= m; pi++) {
        for (int c = 0; c <= 1; c++) {
          int add = (a[i] != ('0' + c));
          int npi = aut[pi][c];
          for (int k = 0; k < n - m + 2; k++) {
            if (npi == m) {
              if (k != 0)
                ndp[{npi, k}] = min(ndp[{npi, k}], dp[{pi, k - 1}] + add);
            } else {
              ndp[{npi, k}] = min(ndp[{npi, k}], dp[{pi, k}] + add);
            }
          }
        }
      }
      swap(dp, ndp);
    }
    for (int k = 0; k <= n - m + 1; k++) {
      int ans = INF;
      for (int pi = 0; pi <= m; pi++) ans = min(ans, dp[{pi, k}]);
      if (ans == INF)
        cout << -1 << " ";
      else
        cout << ans << " ";
    }
  }
  