SP27498 VOTAS - Votka and String

Votka 对字符串非常着迷。最近他学会了如何处理前缀和后缀。在字符串 $S$ 中，前缀指的是从开头到任意位置的一段连续字符，而后缀则是从任意位置到结尾的一段连续字符。例如，字符串“abc”的前缀集合是 {“a”, “ab”, “abc”}，后缀集合是 {“abc”, “bc”, “c”}。若字符串 $S$ 的一个后缀 $S_i$ 至少包含 $b$ 个前缀并且这些前缀也是 $S$ 的前缀，那么这个后缀 $S_i$ 就被称为美丽的。 具体来说， 设 $P$ 是 $S$ 的所有前缀的集合， 而 $P_i$ 是后缀 $S_i$ 的所有前缀的集合。 当 $|P \cap P_i| \ge b$ 时，$S_i$ 就是美丽的后缀。 举个例子，假设 $S = \text{``abcabcd''}$ 并且 $b = 3$，那么后缀 $S_3$, 即“abcd”是一个美丽后缀，因为它具有 3 个（不少于 $b$）前缀 {“a”, “ab”, “abc”}，同时这些也是 $S$ 的前缀。值得注意的是，$S$ 自身对于任意 $b$ 都是美丽的后缀。 现在，Votka 想出了一个问题，给你一个字符串 $S$ 和 $m$ 个整数 $\{K_1, K_2, \ldots, K_m\}$。对于每个整数 $K_i$，你需要找出 $S$ 中满足 $b = K_i$ 的美丽后缀的数量。 Votka 承诺会奖赏第一个解决这个问题的人。作为 Votka 的好友，Luffy 很想得到这个奖励，但他自己解决不了，于是向你求助。你能帮帮他吗？

输入的第一行是一个整数 $T$，表示有多少个测试用例。每个测试用例的第一行是一个字符串 $S$（$1 \le |S| \le 10^5$），字符串仅由小写英文字符组成。接下来一行是一个整数 $m$（$1 \le m \le 10^5$）。接下来这一行中有 $m$ 个整数 $K_1, K_2, \ldots, K_m$（$0 \le K_i \le |S|$），以空格分隔。

对于每一个测试用例，输出一行包含 $m$ 个整数，表示对于每个 $K_i$，$S$ 中美丽后缀的数量。注意：数据量很大，请使用高效的输入输出方式。

- $1 \le T \le 10$ - $1 \le |S| \le 10^5$ - $1 \le m \le 10^5$ - $0 \le K_i \le |S|$ **本翻译由 AI 自动生成**