← 返回题目列表

Codeforces · 2104/E

E. 令人不愉快的字符串

中文机器翻译题面 查看原题

我们来写封信吧 允许 如果它是小写字母并且是拉丁字母表的前 $$$k$$$ 字母之一。

给您一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅包含允许的字母。

让我们调用一个字符串 $$$t$$$ 令人愉快 如果 $$$t$$$ 是 $$$s$$$ 的子序列。

给你 $$$q$$$ 字符串 $$$t_1, t_2, \dots, t_q$$$。所有这些都仅包含允许的字母。对于每个字符串 $$$t_i$$$,计算需要在右侧附加的允许字母的最小数量,以便它 停止 令人愉快。

序列 $$$t$$$ 是序列 $$$s$$$ 的子序列,如果 $$$t$$$ 可以通过从任意位置删除几个(可能是零个或全部)元素从 $$$s$$$ 获得。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 10^6$$$; $$$1 \le k \le 26$$$) — 字符串 $$$s$$$ 的长度和允许的字母数量。

第二行包含字符串 $$$s$$$,由 $$$n$$$ 小写拉丁字母组成。字符串的每个字符都是拉丁字母表中前 $$$k$$$ 字母之一。

第三行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 查询数。

接下来的 $$$q$$$ 行包含查询:每行一个查询。第 $$$i$$$ 行包含字符串 $$$t_i$$$,仅包含允许的字母。

对输入的附加限制:所有 $$$t_i$$$ 的总长度不超过 $$$10^6$$$。

输出

对于每个查询,输出一个整数——需要附加到右侧字符串中的允许字母的最小数量,这样它就不再令人愉快了。

示例

输入
复制

7 3
abacaba
3
cc
bcb
b

输出
复制

0
1
2

输入
复制

5 1
aaaaa
6
a
aa
aaa
aaaa
aaaaa
aaaaaa

输出
复制

5
4
3
2
1
0

注意

在第一个示例中:

  1. 字符串 cc 已经令人不快了,所以不需要添加任何内容;
  2. BCB 令人愉快,因此至少需要在右侧添加一个字母: BCBA 不起作用,但是 bcbb 和 bcbc 令人不愉快。
  3. To b,至少需要附加两个字母,因为 ba, bb,和 bc 令人愉快。例如,我们可以获得一个令人不愉快的字符串 bbb.