CF2104E Unpleasant Strings

Let's call a letter allowed if it is a lowercase letter and is one of the first $ k $ letters of the Latin alphabet. You are given a string $ s $ of length $ n $ , consisting only of allowed letters. Let's call a string $ t $ pleasant if $ t $ is a subsequence of $ s $ . You are given $ q $ strings $ t_1, t_2, \dots, t_q $ . All of them consist only of allowed letters. For each string $ t_i $ , calculate the minimum number of allowed letters you need to append to it on the right so that it stops being pleasant. A sequence $ t $ is a subsequence of a sequence $ s $ if $ t $ can be obtained from $ s $ by the deletion of several (possibly, zero or all) element from arbitrary positions.

The first line contains two integers $ n $ and $ k $ ( $ 1 \le n \le 10^6 $ ; $ 1 \le k \le 26 $ ) — the length of the string $ s $ and the number of allowed letters. The second line contains the string $ s $ , consisting of $ n $ lowercase Latin letters. Each character of the string is one of the first $ k $ letters of the Latin alphabet. The third line contains one integer $ q $ ( $ 1 \le q \le 2 \cdot 10^5 $ ) — the number of queries. The next $ q $ lines contain queries: one query per line. The $ i $ -th line contains the string $ t_i $ , consisting only of allowed letters. Additional constraint on input: the total length of all $ t_i $ does not exceed $ 10^6 $ .

For each query, output one integer — the minimum number of allowed letters that need to be appended to the string on the right so that it stops being pleasant.

In the first example: 1. The string cc is already unpleasant, so nothing needs to be appended to it; 2. bcb is pleasant, so at least one letter needs to be appended to the right: bcba will not work, but bcbb and bcbc are unpleasant. 3. To b, at least two letters need to be appended, since ba, bb, and bc are pleasant. For example, we can obtain an unpleasant string bbb.