SP28315 WEAKSMK - Shoumiks Weakness

Shoumik 非常喜欢解决问题，但在处理与字符串相关的问题时常常感到吃力。 为了提高自己的能力，他决定深入练习字符串问题。他觉得自己创造一个字符串问题并加以解决，是个很好的学习方式。于是他设计了如下的题目。 给定一个长度为 $N$ 的小写字母字符串 $S$，需要你计算出有多少个不同的子串 $T$，满足它的长度为 $L$ 且在字符串 $S$ 中恰好出现了 $X$ 次。 例如，在字符串 $S=\text{“abcbcb”}$ 中，子串 $T=\text{“bcb”}$ 长度为 $L=3$，并且在 $S$ 中恰好出现了 $X=2$ 次。 但由于 Shoumik 对字符串技术仍不够熟练，他被这个问题难住了。你需要帮助他回答关于给定字符串 $S$ 的 $Q$ 次查询。 ### 输入格式 第一行输入包含一个整数 $T_s$，表示测试用例的数量。 接下来的每个测试用例开始于一行包含两个整数 $N$ 和 $Q$。随后的一行是由 $N$ 个小写字母组成的字符串 $S$。接下来有 $Q$ 行，每行包含两个整数 $L$ 和 $X$，分别表示子串 $T$ 的目标长度以及 $T$ 在 $S$ 中出现的次数。 ### 输出格式 对于每个查询，输出满足条件的长度为 $L$ 且在 $S$ 中恰好出现 $X$ 次的不同子串 $T$ 的数量。 ### 数据范围与提示 - $1 \le T_s \le 15$ - $1 \le N \le 10000$ - $1 \le Q \le 100000$ - $1 \le L < 2^{31}$ - $0 \le X < 2^{31}$ - 所有测试用例中 $N$ 的总和不超过 $60000$ - 所有测试用例中 $Q$ 的总和不超过 $600000$ ### 样例 ``` 输入： 1 6 5 abcbcb 3 2 4 1 6 2 6 1 1 2 输出： 1 3 0 1 1 ``` **本翻译由 AI 自动生成**

无

无