Description

Gagan 刚刚收到她的朋友 Jorge 发来的邮件。邮件中包含重要信息，但不幸的是在传输过程中内容被损坏了：所有的空格都被移除了，并且在移除空格后，有些字母还被替换成了其他字母！现在 Gagan 只剩下一个由小写字母组成的字符串 $\mathbf{S}$。

你知道，这封邮件最初是由下述字典中的单词组成的。此外，你还知道字母是在空格被移除之后才发生更改的，并且任意两次字母更改的位置之间的距离不少于 $5$。举例来说，字符串 "code jam" 可能变成 "codejam"、"dodejbm"、"zodejan" 或 "cidejab"，但不能变成 "kodezam"（因为 "k" 和 "z" 这两个更改之间的距离只有 $4$）。

你需要求出，为了能将 $\mathbf{S}$ 还原为由字典单词拼成的字符串，最少需要修改多少个字母。

字典包含 $\mathbf{W}$ 个单词，每个单词长度在 $1$ 到 $10$ 个小写字母之间，字典会在输入文件开头给出。这个字典不是任何自然语言的字典，尽管其中包含一些英文单词。对于同一个输入文件的所有测试用例，字典都是相同的。字典中的单词按字典序递增排列，且不会有重复单词。

Input Format

输入的第一行为字典单词数 $\mathbf{W}$。接下来的 $\mathbf{W}$ 行，每行一个小写字母字符串，表示字典中的一个单词。再下一行是测试用例数 $\mathbf{T}$。随后有 $\mathbf{T}$ 个测试用例，每个测试用例占一行，包含一个仅由小写字母组成的字符串 $\mathbf{S}$。

Output Format

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 为测试用例编号（从 $1$ 开始），$y$ 为将 $\mathbf{S}$ 还原为字典单词拼接而成的字符串所需的最少字母修改次数。

9
aabea
bobs
code
in
jam
oo
operation
production
system
4
codejam
cxdejax
cooperationaabea
jobsinproduction

Case #1: 0
Case #2: 2
Case #3: 1
Case #4: 1

Hint

样例说明

"code" 和 "jam" 都在字典中。虽然 "cooperation" 是英语单词，但它不在字典中；"aabea" 在字典中。

注意，为了便于展示样例，样例中的字典规模并不符合实际数据范围。

限制条件

• $W = 521196$
• 字典中每个单词长度为 $1$ 到 $10$ 个小写字母
• 字典按字典序递增排列
• 字典中无重复单词
• 字典总字符数为 $3323296$
• $\mathbf{S}$ 是合法的：一定存在一种上述方式生成 $\mathbf{S}$

小数据集（12 分，测试集 1 - 可见）

• 时间限制：30 3 秒
• $1 \leq T \leq 20$
• $1 \leq \mathbf{S}$ 长度 $\leq 50$

大数据集（24 分，测试集 2 - 隐藏）

• 时间限制：60 6 秒
• $1 \leq T \leq 4$
• $1 \leq \mathbf{S}$ 长度 $\leq 4000$

翻译由 ChatGPT-4.1 完成。