#P2536. [AHOI2005] 病毒检测

    ID: 1544 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>AC 自动机字符串概率论统计各省省选2005安徽字典树Trie 树

[AHOI2005] 病毒检测

题目描述

科学家们在 Samuel 星球上的探险仍在继续。非常幸运的,在 Samuel 星球的南极附近,探险机器人发现了一个巨大的冰湖!机器人在这个冰湖中搜集到了许多 RNA 片段运回了实验基地。

科学家们经过几个昼夜的研究,发现这些 RNA 片段中有许多是未知的病毒!

每个 RNA 片段都是由 ACTG 组成的序列。科学家们也总结出了 Samuel 星球上的“病毒模版片段”。一个模版片段是由 ACTG 的序列加上通配符 *? 来表示。其中 * 的意思是可以匹配上 00 个或任意多个字符,而 ? 的意思是匹配上任意一个字母。

如果一个 RNA 片段能够和“病毒模版片段”相匹配,那么这个 RNA 片段就是未知的病毒。

例如,假设 “病毒模版片段”为 A*G?C。RNA 片段:AGTCAGTGTC 都是未知的病毒,而 RNA 片段 AGTGC 则不是病毒。

由于,机器人搜集的这些 RNA 片段中除去病毒的其他部分都具有非常高的研究价值。所以科学家们希望能够分辨出其中哪些 RNA 片段不是病毒,并将不是病毒的 RNA 片段运回宇宙空间站继续进行研究。

科学家将这项任务交给了小联。现在请你为小联编写程序统计哪些 RNA 片段不是病毒。

输入格式

N+2N+2 行输入。

第一行有一个字符串,由 ACTG*? 组成,表示“病毒模版片段”。“病毒模版片段”的长度不超过 10001000

第二行有一个整数 NN,表示机器人搜集到的 RNA 片段的数目。

随后的 NN 行,每一行有一个字符串,由 ACTG 组成,表示一个 RNA 片段。

输出格式

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

A*G?C
3
AGTC
AGTGTC
AGTGC
1

提示

输入中的 RNA 片段 AGTGC 不是病毒。

对于所有数据,0<N<5000 < N < 500

特别的:

  • 每个 RNA 片段的长度不超过 500500
  • “病毒模版片段”和 RNA 片段的长度都至少为 11