#MX104. 差异

差异

题目描述

对于两个长度相等的字符串 s,ts,t,若 s,ts,t 不同的位数不超过 kk,则称 (s,t)(s,t) 关系很好。

现在给定长度为 nn 的字符串 SS,对于每个 1≤i≤n−11\le i\le n-1,记字符串 AA 为 SS 的前 ii 位,BB 为 SS 的后 n−in-i 位。

现在 a,ba,b 分别为 A,BA,B 的子串,求出有多少对 (a,b)(a,b) 关系很好。

输入格式

第一行两个整数 n,kn,k,意义如题述。

第二行一个字符串 SS。

输出格式

共 n−1n-1 行,每行一个整数,表示答案。

样例 1 输入

4 0
abca

样例 1 输出

1
1
1

样例 1 说明

一直都有且仅有 (a,a)(\texttt a,\texttt a) 关系很好。

样例 2 输入

6 1
abcadd

样例 2 输出

5
9
10
8
5

数据规模与约定

  • 测试点 11:SS 仅由一种字符构成;
  • 测试点 2∼32\sim 3:n≤10n\le 10;
  • 测试点 4∼64\sim 6:n≤100n\le 100。
  • 测试点 7∼107\sim 10:无特殊限制。