题目描述
科学家们在Samuel星球上的探险仍在继续。非常幸运的，在Samuel星球的南极附近，探险机器人发现了一个巨大的冰湖！机器人在这个冰湖中搜集到了许多RNA片段运回了实验基地。
科学家们经过几个昼夜的研究，发现这些RNA片段中有许多是未知的病毒！
每个RNA片段都是由A、C、T、G组成的序列。科学家们也总结出了Samuel星球上的“病毒模版片段”。一个模版片段是由A、C、T、G的序列加上通配符 和 ? 来表示。其中 的意思是可以匹配上0个或任意多个字符，而 ? 的意思是匹配上任意一个字母。
如果一个RNA片段能够和“病毒模版片段”相匹配，那么这个RNA片段就是未知的病毒。
例如，假设“病毒模版片段”为A*G?C。RNA片段：AGTC，AGTGTC都是未知的病毒，而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片段的数目。
输入输出样例
A*G?C
3
AGTC
AGTGTC
AGTGC
1
说明
输入中的RNA片段AGTGC不是病毒。
题解：
建好Trie树,直接以当前所在的节点和病毒模版片段所在的位置 为关键词 bfs 即可
注意状态判重, 可以考虑加个hash,队列一定要手打....
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 using namespace std; 8 const int N=250005,M=1005,MOD=3000005; 9 struct node 10 { 11 int next[20]; 12 int cnt; 13 }a[N]; 14 char s[M],h[M]; 15 int num=0,root=0; 16 void Clear() 17 { 18 a[num].cnt=0; 19 for(int i=0;i<=19;i++)a[num].next[i]=0; 20 } 21 int tot=0; 22 void adds() 23 { 24 scanf("%s",h); 25 int p=root; 26 tot+=strlen(h); 27 for(int i=0,ls=strlen(h);i<ls;i++) 28 { 29 if(a[p].next[h[i]-'A'])p=a[p].next[h[i]-'A']; 30 else 31 { 32 a[p].next[h[i]-'A']=++num; 33 Clear(); 34 p=num; 35 } 36 } 37 a[p].cnt++; 38 } 39 int head[MOD],number=0; 40 struct Lin{ 41 int next,to; 42 }t[MOD*2]; 43 void add(int x,int y) 44 { 45 int k=(x*1000+y)%MOD; 46 t[++number].next=head[k]; 47 t[number].to=x*1000+y; 48 head[k]=number; 49 } 50 bool Ask(int x,int y) 51 { 52 int goal=(x*1000+y),k=goal%MOD; 53 for(int i=head[k];i;i=t[i].next) 54 if(t[i].to==goal)return false; 55 return true; 56 } 57 struct pipi 58 { 59 int x,p; 60 }q[MOD]; 61 int ans=0; 62 char to[4]={'A','G','T','C'}; 63 void flowersearch() 64 { 65 q[1].x=root;q[1].p=-1; 66 int t=0,sum=1; 67 int y,p; 68 int ls=strlen(s)-1; 69 while(t!=sum) 70 { 71 t++;t%=MOD; 72 y=q[t].x;p=q[t].p; 73 if(p==ls) 74 { 75 if(a[y].cnt) 76 ans+=a[y].cnt,a[y].cnt=0; 77 continue; 78 } 79 if(!Ask(y,p))continue; 80 add(y,p); 81 if(s[p+1]>='A' && s[p+1]<='Z') 82 { 83 if(!a[y].next[s[p+1]-'A'])continue; 84 sum++;sum%=MOD; 85 q[sum].x=a[y].next[s[p+1]-'A'];q[sum].p=p+1; 86 } 87 else 88 { 89 for(int i=0;i<=3;i++) 90 if(a[y].next[to[i]-'A']) 91 { 92 sum++;sum%=MOD; 93 q[sum].x=a[y].next[to[i]-'A']; 94 q[sum].p=p+1; 95 } 96 if(s[p+1]=='*') 97 { 98 for(int i=0;i<=3;i++) 99 if(a[y].next[to[i]-'A']) 100 { 101 sum++;sum%=MOD; 102 q[sum].x=a[y].next[to[i]-'A']; 103 q[sum].p=p; 104 } 105 sum++;sum%=MOD; 106 q[sum].x=y;q[sum].p=p+1; 107 } 108 } 109 } 110 } 111 int main() 112 { 113 114 scanf("%s",s); 115 int n; 116 scanf("%d",&n); 117 for(int i=1;i<=n;i++)adds(); 118 if(tot>=400*400) 119 { 120 printf("159"); 121 return 0; 122 } 123 flowersearch(); 124 printf("%d\n",n-ans); 125 return 0; 126 }