P13428 [GCJ 2009 Qualification] Alien Language

经过多年的研究，Google Labs 的科学家们发现了一种来自遥远星球的外星语言。这种外星语言非常独特，每个单词恰好由 $L$ 个小写字母组成。此外，这种语言中恰好有 $D$ 个单词。 在建立了该外星语言所有单词的字典后，科学家们的下一个重大突破是发现，外星人在过去十年间一直在向地球发送信息。不幸的是，由于两颗星球之间的距离遥远，这些信号在传输过程中被削弱，导致部分单词可能被误解。为了帮助科学家们解读这些信息，他们请你设计一个算法，能够判断给定模式下可能的解释数量。 一个模式恰好由 $L$ 个**符号**组成。每个符号要么是一个小写字母（科学家们非常确定这就是那个字母），要么是由圆括号括起来的一组互不相同的小写字母。例如：(ab)d(dc) 表示第一个字母可以是 a 或 b，第二个字母一定是 d，第三个字母可以是 d 或 c。因此，模式 (ab)d(dc) 可能代表以下 4 种情况之一：add、adc、bdd、bdc。

输入的第一行包含 3 个整数 $L$、$D$ 和 $N$，以空格分隔。接下来的 $D$ 行，每行一个长度为 $L$ 的单词，表示该外星语言已知的单词。所有已知单词保证互不相同。接下来有 $N$ 个测试用例，每个测试用例一行，均为如上描述的模式。

对于每个测试用例，输出 Case #$X$: $K$ 其中 $X$ 表示测试用例编号（从 1 开始），$K$ 表示有多少个外星语言中的单词与该模式匹配。

**限制条件** **小数据集（10 分）** - $1 \leq L \leq 10$ - $1 \leq D \leq 25$ - $1 \leq N \leq 10$ **大数据集（23 分）** - $1 \leq L \leq 15$ - $1 \leq D \leq 5000$ - $1 \leq N \leq 500$ 翻译由 ChatGPT-4.1 完成。