P13222 [GCJ 2015 #1C] Typewriter Monkey

你的出版社决定让猴子随机敲击键盘来创作伟大的文学作品。你是一个猴子的监督员，这只猴子的键盘上有 $K$ 个按键，每个按键上都标有一个大写英文字母（同一个字母可能出现在多个按键上）。猴子将从一个空字符串开始，重复 $S$ 次以下操作：从键盘上等概率随机选择一个按键并按下，将该按键上的字母添加到字符串的末尾。最终得到的字符串长度为 $S$。 你有一个长度为 $L$ 的*目标单词*，你希望猴子能够敲出来（目标单词不一定是真正的英文单词）。这个目标单词可能在猴子敲出的字符串中出现多次（重叠的情况也算，例如目标单词为 "ABA"，猴子敲出 "ABABA" 时，包含两个 "ABA"）。 你打算每出现一次目标单词就给猴子一根香蕉。当你去检查猴子的作品时，你会带上足够多的香蕉，以保证无论猴子敲出了什么，你都能支付得起。然后，你会根据猴子实际敲出的目标单词次数支付香蕉，剩下的香蕉归你所有。 你期望最终能留下多少根香蕉？

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据包含三行： 第一行包含三个用空格分隔的正整数：$K$、$L$ 和 $S$。 第二行为一个长度为 $K$ 的仅包含大写英文字母的字符串，表示猴子的键盘。 第三行为一个长度为 $L$ 的仅包含大写英文字母的字符串，表示目标单词。

对于每组测试数据，输出一行，格式为 "Case #$x$: $y$"，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为你期望能留下的香蕉数。 如果 $y$ 的绝对误差或相对误差在 $10^{-6}$ 以内，则视为正确。

**样例解释** 注意，第 5 组样例不在 Small 数据集的范围内。 在第 1 组样例中，猴子根本无法敲出目标单词 "MONKEY"（因为键盘上缺少目标单词中的大部分字母），所以你无需带香蕉，也不会支付任何香蕉。可怜的猴子！ 在第 2 组样例中，猴子一定会敲出 "AAAA"，其中目标单词 "AAA" 会出现两次（重叠），你需要带两根香蕉并全部支付出去。 在第 3 组样例中，猴子可能敲出的字符串有 "AA"、"AB"、"BA"、"BB"，每种概率均为 $1/4$，它们分别包含 0、1、1、2 次目标单词。你需要带两根香蕉以备 "BB" 的情况，但平均支付 $(0 + 1 + 1 + 2) / 4 = 1$ 根香蕉。 在第 4 组样例中，猴子第一步有 $1/3$ 的概率敲 "G"，第二步有 $1/3$ 的概率敲 "O"，所以敲出 "GO" 的概率为 $1/9$，你需要带一根香蕉，并在 $1/9$ 的情况下支付出去。 在第 5 组样例中，理论上猴子最多能敲出 9 次 "ROSENCRANTZ"，但实际出现一次的概率都极小，可以忽略不计。 **数据范围** $1 \leq T \leq 100$。 **小数据集（11 分）** - 时间限制：~~240~~ 5 秒。 - $1 \leq K \leq 7$。 - $1 \leq L \leq S \leq 7$。 **大数据集** - 时间限制：~~480~~ 10 秒。 - $1 \leq K \leq 100$。 - $1 \leq L \leq S \leq 100$。 由 ChatGPT 4.1 翻译