AT_ttpc2022_e.Name Value

大学 A 和大学 B 决定合并。大学 A 的名字为 $A$，大学 B 的名字为 $B$。现在我们需要为合并后的新大学起一个名字 $C$，具体规定如下：

• 从 $A$ 的所有非空子序列中选取一个，记为 $a$。
• 从 $B$ 的所有非空子序列中选取一个，记为 $b$。
• 新大学名 $C$ 是将 $a$ 和 $b$ 按顺序连接得到的字符串。

现在给定 $Q$ 个字符串 $S_1, S_2, \dots, S_Q$。请你判断每个字符串能否作为 $C$ 出现。如果可以，请求出所有可能的 $|\text{len}(a) - \text{len}(b)|$ 中的最小值（$\text{len}(x)$ 表示 $x$ 的长度）；如果不可以，输出 $-1$。

什么是子序列？对于字符串 $X$，通过去除 $0$ 个及以上字符后，按照原本顺序排列剩下的字符所得的字符串称为 $X$ 的子序列。例如，ac 和 abc 都是 abc 的子序列，但 ca 不是 abc 的子序列。

输入按以下格式从标准输入读入：

$A$ $B$ $Q$ $S_1$ $S_2$ $\vdots$ $S_Q$

输出 $Q$ 行。对于每个 $1 \leq i \leq Q$，如果 $S_i$ 可能作为 $C$，则输出 $|\text{len}(a) - \text{len}(b)|$ 的最小值；否则输出 $-1$。

部分分

• 对于 $Q \leq 20$ 的数据集，得分为 $100$ 分。

样例解释 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$ 不能是空串。
• 与常规题目不同，空格也是字符串的一部分，需要注意。

数据范围

• $Q$ 是整数。
• $1 \leq Q \leq 10^6$。
• $A, B, S_1, S_2, \dots, S_Q$ 都是由小写英文字母、大写英文字母及空格组成的字符串。
• $1 \leq \text{len}(A), \text{len}(B) \leq 10^5$。
• $2 \leq \text{len}(S_i) \leq 10^5$（$1 \leq i \leq Q$）。
• $\displaystyle\left(\sum_{i = 1}^Q\text{len}(S_i)\right) \leq 2 \times 10^6$。

由 ChatGPT 5 翻译