← 返回题目列表

AtCoder · ttpc2022_e

E. 名称 值

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

配点 : 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 不能为空。
  • 与一般问题不同,请注意空格也是字符串的一部分。