// Author: Aquizahv #include <bits/stdc++.h> #define ull unsigned long long #define ll long long using namespace std; const int N = 1e5 + 5, base = 29, K = 40, pre = 32; int n, m, k; char s[N], t[N]; int f[K][K << 1], mn[K << 1], ans[K]; ull hashs[N], hasht[N], p[N]; void init() { p[0] = 1; for (int i = 1; i <= 1e5; i++) p[i] = p[i - 1] * base; ull x = 0; for (int i = 1; i <= n; i++) { x = x * base + (s[i] - 'a'); hashs[i] = x; } x = 0; for (int i = 1; i <= m; i++) { x = x * base + (t[i] - 'a'); hasht[i] = x; } } ull Hashs(int l, int r) { return hashs[r] - (hashs[l - 1] * p[r - l + 1]); } ull Hasht(int l, int r) { return hasht[r] - (hasht[l - 1] * p[r - l + 1]); } int LCP(int i, int j) { if (i > n || j > m) return 0; int l = 0, r = min(n - i + 1, m - j + 1), res = 0; while (l <= r) { int mid = (l + r) >> 1; if (Hashs(i, i + mid - 1) == Hasht(j, j + mid - 1)) { res = mid; l = mid + 1; } else r = mid - 1; } return res; } inline void Max(int &to, int fro) { to = max(to, fro); } void DP(int st) { memset(f, -0x40, sizeof(f)); f[0][pre] = LCP(1, st + 1); // cout << st << ' ' << LCP(1, st + 1) << endl; for (int i = 0; i < k;) { for (int j = -i; j <= i; j++) { // cout << i << ' ' << j << endl; int fij = f[i][j + pre]; // insert if (st + fij + j < m) Max(f[i + 1][pre + j + 1], fij); // erase Max(f[i + 1][pre + j - 1], min(n, fij + 1)); // update if (st + fij + j < m) Max(f[i + 1][pre + j], min(n, fij + 1)); } i++; for (int j = -i; j <= i; j++) if (f[i][pre + j] >= 0) f[i][pre + j] += LCP(f[i][pre + j] + 1, st + f[i][pre + j] + j + 1); // for (int j = -k; j <= k; j++) // printf("%d%c", f[i][pre + j] < 0 ? -1 : f[i][pre + j], " \n"[j == k]); } memset(mn, -1, sizeof(mn)); for (int i = k; i >= 0; i--) for (int j = -i; j <= i; j++) if (f[i][j + pre] + j > 0 && f[i][j + pre] >= n) mn[j + pre] = i; for (int i = -k; i <= k; i++) if (mn[i + pre] != -1) ans[mn[i + pre]]++; } int main() { #ifndef ONLINE_JUDGE freopen("data.in", "r", stdin); freopen("data.out", "w", stdout); #endif cin >> k; scanf("%s%s", s + 1, t + 1); n = strlen(s + 1), m = strlen(t + 1); init(); for (int i = 0; i < m; i++) DP(i); for (int i = 0; i <= k; i++) printf("%d\n", ans[i]); // cout << "Eden" << endl; return 0; }