配点 : 200 点
問題文
大学 A 和大学 B 决定合并。大学 A 的校名是 A ,大学 B 的校名是 B 。合并后的新大学名称 C 我们来考虑一下。具体来说,按照以下方式 C 。 对于
- A 取非空的子序列 1 个,并将 a 。
- B 取非空的子序列 1 个,并将 b 。
- C 该值应乘以 a 和 按字典顺序比较 b 按这个顺序连接成字符串。
Q 字符串 S_1, S_2, \dots, S_Q 已经给出。请判断每个字符串是否有可能是 C ,如果有可能,请求出作为|\text{len}(a) - \text{len}(b)| 可能的最小值。( \text{len}(x) 是 您也可以写 x 的长度) 什么是
子序列? 对于
文字列 X ,将构成该字符串的字符中 0 个或以上的字符移除,并按原顺序排列剩余的字符所得到的字符串 称为 S 的子序列。例如,ac 呀
请注意,它可能是 abc 是
您也可以写 abc 的子序列,ca 是
您也可以写 abc 的子序列。
制約
- Q 是一个整数。
- 1 ≤ Q ≤ 10^6
- A, B, S_1, S_2, \dots, S_Q 是由英文字母小写、英文字母大写及空白构成的字符串。
- 1 ≤ \text{len}(A), \text{len}(B) ≤ 10^5
- 2 ≤ \text{len}(S_i) ≤ 10^5 (1 ≤ i ≤ Q)
- \displaystyle\left(\sum_{i = 1}^Q\text{len}(S_i)\right) ≤ 2 \times 10^6
部分点
- Q ≤ 20 的数据集 如果可以作为 100 点。 如果您正确回答了所有满足
入力
输入是按以下格式从标准输入给出的。
A B Q S_1 S_2 \vdots S_Q
出力
Q 行。i 行目 (1 ≤ i ≤ Q) 中,
希望变为S_i 是
在 C 则作为 |\text{len}(a) - \text{len}(b)| 的最小值,如果不可能的话 -1 。
入力例 1
Tokyo Institute of Technology Tokyo Medical and Dental University 10 The University Tokyo University kyoto University Tokyo Tech TMDU Kyoto University The University of Tokyo Tokyo Technology and Medical and Dental University Tehnoooorsty Tokyo
出力例 1
10 4 4 -1 2 -1 -1 -1 3 1
- S_1 = {}
The University, 当我输入a = {}Th、b = {}e University以C = {}The University可以这样做。这时,请注意,|\text{len}(a) - \text{len}(b)| = 10 。 对于 - S_4 = {}
Tokyo Tech, 当我输入b 不能为空。 - 与一般问题不同,请注意空格也是字符串的一部分。