P13290 [GCJ 2013 #1B] Garbled Email

Gagan 刚刚收到她的朋友 Jorge 发来的邮件。邮件中包含重要信息，但不幸的是在传输过程中内容被损坏了：所有的空格都被移除了，并且在移除空格后，有些字母还被替换成了其他字母！现在 Gagan 只剩下一个由小写字母组成的字符串 $\mathbf{S}$。 你知道，这封邮件最初是由下述字典中的单词组成的。此外，你还知道字母是在空格被移除之后才发生更改的，并且**任意两次字母更改的位置之间的距离不少于 $5$**。举例来说，字符串 "code jam" 可能变成 "codejam"、"dodejbm"、"zodejan" 或 "cidejab"，但不能变成 "kodezam"（因为 "k" 和 "z" 这两个更改之间的距离只有 $4$）。 你需要求出，为了能将 $\mathbf{S}$ 还原为由字典单词拼成的字符串，**最少需要修改多少个字母**。 字典包含 $\mathbf{W}$ 个单词，每个单词长度在 $1$ 到 $10$ 个小写字母之间，字典会在输入文件开头给出。这个字典不是任何自然语言的字典，尽管其中包含一些英文单词。对于同一个输入文件的所有测试用例，字典都是相同的。字典中的单词按字典序递增排列，且不会有重复单词。

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

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

**样例说明** "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 完成。