#include<bits/stdc++.h> using namespace std; #define int long long const int N = 3005; int n, k; char c[N]; int diff[N]; // 差分数组 signed main(){ cin >> n >> k; for(int i=1;i<=n;i++) cin >> c[i]; // 枚举每一条对角线 d = y - x > 0 for(int d = 1; d <= n-1; d++){ int cnt = 0; // 当前窗口失配数量 int r = 0; // x是sa，y=x+d是sb for(int x = 1; x + d <= n; x++){ int y = x + d; // 【r只往右走，不回退！】双指针核心 if(r < x) { r = x; cnt = 0; } // 尽可能向右扩展 r+1 while(r+1 <= n && (r+1 + d) <= n){ int nx = r+1; int ny = nx + d; if(c[nx] != c[ny]){ if(cnt == k) break; cnt++; } r++; } // 现在 [x, r] 是合法区间，最长长度 L = r - x + 1 int L = r - x + 1; // 差分：对 i ∈ [x, y-1] += L, y=x+d diff[x] += L; diff[y] -= L; } } // 差分前缀和，输出答案 int now = 0; for(int i=1;i<=n-1;i++){ now += diff[i]; cout << now << '\n'; } return 0; }