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;
  short D[501][501][501], PI[500], RPI[500][2];
  string s, t;
  void getPI(const string& s) {
    int N = s.size(), j = 0;
    for (int i = 1; i < N; i++) {
      while (j && s[i] != s[j]) j = PI[j - 1];
      if (s[i] == s[j]) PI[i] = ++j;
    }
  }
  int get_pos(int p, char v) {
    if (p == 0 || t[p] == v) return RPI[p][v - '0'] = p;
    if (RPI[p][v - '0'] > -1) return RPI[p][v - '0'];
    return RPI[p][v - '0'] = get_pos(PI[p - 1], v);
  }
  int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N, M, m, v;
    cin >> N >> M >> s >> t;
    getPI(t);
    memset(RPI, -1, sizeof(RPI));
    memset(D, 0x7f, sizeof(D));
    if (s[0] == t[0]) {
      if (M == 1)
        D[0][0][1] = 0;
      else
        D[0][1][0] = 0;
      D[0][0][0] = 1;
    } else {
      if (M == 1)
        D[0][0][1] = 1;
      else
        D[0][1][0] = 1;
      D[0][0][0] = 0;
    }
    for (int i = 1; i < N; i++)
      for (int j = 0; j <= i; j++)
        for (int k = 0; k <= i; k++)
          if ((m = D[i - 1][j][k]) <= N) {
            v = j;
            if (v && s[i] != t[v]) v = get_pos(v, s[i]);
            if (s[i] == t[v]) {
              if (++v == M)
                D[i][PI[M - 1]][k + 1] = min(D[i][PI[M - 1]][k + 1], (short)m);
              else
                D[i][v][k] = min(D[i][v][k], (short)m);
            } else
              D[i][v][k] = min(D[i][v][k], (short)m);
            v = j;
            if (v && s[i] == t[v]) v = get_pos(v, '1' - s[i] + '0');
            if (s[i] != t[v]) {
              if (++v == M)
                D[i][PI[M - 1]][k + 1] =
                    min(D[i][PI[M - 1]][k + 1], (short)(m + 1));
              else
                D[i][v][k] = min(D[i][v][k], (short)(m + 1));
            } else
              D[i][v][k] = min(D[i][v][k], (short)(m + 1));
          }
    for (int i = 0; i < N - M + 2; i++) {
      m = N + M;
      for (int j = 0; j < M; j++) m = min((short)m, D[N - 1][j][i]);
      cout << (m <= N ? m : -1) << ' ';
    }
    return 0;
  }
  