C1463 [AHOI2005]病毒检测

内存限制:256 MB 时间限制:3000 ms

题目描述

科学家们在 Samuel 星球上的探险仍在继续。非常幸运的,在 Samuel 星球的南极附近,探险机器人发现了一个巨大的冰湖!机器人在这个冰湖中搜集到了许多 RNA 片段运回了实验基地。科学家们经过几个昼夜的研究,发现这些 RNA 片段中有许多是未知的病毒!每个 RNA 片段都是由 A、C、T、G 组成的序列。科学家们也总结出了 Samuel 星球上的“病毒模版片段”。一个模版片段是由 A、C、T、G 的序列加上通配符和 ? 来表示。其中的意思是可以匹配上 $0$ 个或任意多个字符,而 ? 的意思是匹配上任意一个字母。如果一个 RNA 片段能够和“病毒模版片段”相匹配,那么这个 RNA 片段就是未知的病毒。例如,假设“病毒模版片段”为A*G?C。RNA 片段:AGTCAGTGTC都是未知的病毒,而 RNA 片段AGTGC则不是病毒。由于,机器人搜集的这些 RNA 片段中除去病毒的其他部分都具有非常高的研究价值。所以科学家们希望能够分辨出其中哪些 RNA 片段不是病毒,并将不是病毒的 RNA 片段运回宇宙空间站继续进行研究。科学家将这项任务交给了小联。现在请你为小联编写程序统计哪些 RNA 片段不是病毒。

输入格式

第一行有一个字符串,由 A、C、T、G、*、? 组成。表示“病毒模版片段”。“病毒模版片段”的长度不超过 $1000$。第二行有一个整数 $N(0<N<500)$,表示机器人搜集到的 RNA 片段的数目。随后的 $N$ 行,每一行有一个字符串,由 A、C、T、G 组成,表示一个 RNA 片段。每个 RNA 片段的长度不超过 $500$。注意:“病毒模版片段”和 RNA 片段的长度都至少为 $1$。

输出

只有一行输出,为整数 $M$,即不是病毒的 RNA 片段的数目。

样例

样例输入 1

A*G?C 3 AGTC AGTGTC AGTGC

样例输出 1

1

提示