CF2104E.Unpleasant Strings

我们称一个字母是允许的，当且仅当它是小写字母且属于拉丁字母表的前 $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$。

对于每个查询，输出一个整数——最少需要在字符串右侧追加的允许字母数量，使其不再愉快。

在第一个样例中：

1. 字符串 cc 已经是不愉快的，因此不需要追加任何字母；
2. bcb 是愉快的，因此至少需要在右侧追加一个字母：bcba 仍然会保持愉快，但 bcbb 和 bcbc 是不愉快的；
3. 对于 b，至少需要追加两个字母，因为 ba、bb 和 bc 都是愉快的。例如，我们可以得到一个不愉快的字符串 bbb。

翻译由 DeepSeek V3 完成