Description
科学家们在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片段不是病毒。
Input
第一行有一个字符串，由A、C、T、G、*、? 组成。表示“病毒模版片段”。“病毒模版片段”的长度不超过1000。第二行有一个整数N（0<N<500），表示机器人搜集到的RNA片段的数目。随后的N行，每一行有一个字符串，由A、C、T、G组成，表示一个RNA片段。每个RNA片段的长度不超过500。注意：“病毒模版片段”和RNA片段的长度都至少为1。
Output
只有一行输出，为整数M，即不是病毒的RNA片段的数目。
数据范围小所以n3能过。。
模板显然是一个简单的正则表达式，所以建一个NFA然后就可以O(n2)判定一个串是否匹配了，总复杂度还是 O(n3)
#include<cstdio> #include<vector> #include<cstring> int n,ans=0; char s[512]; int cid[256],p=1; std::vector<int>nx[512][5]; bool d[512],d1[512]; void adde(int a,int b,int c){ nx[a][b].push_back(c); } int main(){ for(int i=0;i<5;i++)cid["ATGC#"[i]]=i; scanf("%s",s+1); int l=strlen(s+1),w=1,w2=0; s[0]=s[++l]='#'; for(int i=0;i<=l;i++){ int c=s[i],u=++p; if(c=='*'){ if(!w2){ for(c=0;c<5;c++)adde(w,c,u),adde(u,c,u); w2=w;w=u; } }else if(c=='?'){ for(c=0;c<5;c++)adde(w,c,u); if(w2){ for(c=0;c<5;c++)adde(w2,c,u); w2=0; } w=u; }else{ c=cid[c]; adde(w,c,u); if(w2)adde(w2,c,u),w2=0; w=u; } } scanf("%d",&n); while(n--){ scanf("%s",s+1); int len=strlen(s+1); s[0]=s[++len]='#'; memset(d1,0,512); d1[1]=1; for(int i=0;i<=len;i++){ memcpy(d,d1,p+1); memset(d1,0,p+1); int c=cid[s[i]]; for(int j=1;j<=p;j++)if(d[j]){ for(int k=0;k<nx[j][c].size();k++)d1[nx[j][c][k]]=1; } } if(!d1[p])++ans; } printf("%d",ans); return 0; }