#133. T1-徐老师点名了
T1-徐老师点名了
在信息学课上,徐老师要按照份“名单”点名。名单里有 个候选字符串名字 。
他原本准备用一个目标字符串 来精确匹配,但由于录入失误, 的某些位置被没写清楚,变成了 # —— 导致这些位置看不清究竟是哪一个小写字母。
我们说某个字符串 可能与 相同,当且仅当:把 中所有 # 位置分别替换为某个小写字母后,能使其与 在每一位都完全一致。
(特别地,若 ,则无论如何替换都不可能相同。)
现在,请你告诉徐老师:名单里共有多少个字符串可能与 相同。
输入格式
- 第一行:一个字符串 。其中
#表示该位置不确定,可替换为任意小写字母a–z;其余已知位置均为小写字母。 - 第二行:一个正整数 ,表示名单中字符串的数量。
- 接下来 行:第 行给出一个字符串 。保证所有 均由小写字母组成。
输出格式
输出一行一个整数,表示有多少个 可能与 相同。
样例
##c
3
abc
bbc
acb
2
样例解释
的前两位是 #(可任意小写字母),第三位为 c。
候选串依次为 abc、bbc、acb。前两者的第三位都是 c,可以通过合适替换使之与 完全一致;第三个字符串第三位为 b,无法匹配。因此答案为 。
数据范围
对于 的数据,保证 ,所有字符串长度不超过 。
其它数据规模与约定如下表:
| 测试点 | 特殊性质 | |
|---|---|---|
| 无 | ||
中至多只有 个# |
||
| 所有字符串长度相等 | ||
| 无 |