题面链接：[AHOI2005]病毒检测。

思路

本题是 trie 树的简单应用。

首先，问题的转化（~~当然，这是显然的~~）。要求非病毒的片段数量，只需先求出病毒的数量，再用总数去减即可。

我们将要检测的 RNA 片段存入 trie 树，再利用 dfs ，用模板串与它们匹配。

dfs 函数的两个参数可设为：一个是在 trie 树的位置，一个是模板串的“光标”。从(0,0)开始 dfs，匹配一个，模板串的“光标”向前移动一个单位：

如果当前“光标”位置是A、C、T、G，直接去对应当前 trie 树节点的儿子即可。
如果当前“光标”位置是?，往当前 trie 树节点的每一个儿子对应 $1$ 遍（?可匹配四个字母）。
如果当前“光标”位置是*，分三种情况：
- 当作空串。仅模板串的“光标”向前移动，trie 树不变。
- 当作?。同第二种情况。
- 当作?+*。同上。
这样就可以将*给拆成若干?从而解决问题。

一旦某一位匹配成功了，我们如果还有状态到达这一步就没有什么必要了，所以开一个记忆化数组来进行记忆化就好了。

CODE

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	int getid(char ch)
	{
		switch(ch)
		{
			case 'A': return 1;
			case 'C': return 2;
			case 'T': return 3;
			case 'G': return 4;
			default: return 5;
		}
	}
	
	#define mset(a) memset(a,0,sizeof(a))
	struct Trie
	{
		int index=0;
		struct Node
		{
			int son[10],exist;
			Node(){mset(son);exist=0;}
		}node[500000+10];
		
		Trie(){mset(node);}
		
		void insert(char s[])
		{
			int root=0,len=strlen(s);
   			for(int i=0;i<=len-1;i++)
    		{
        		int sons=getid(s[i]);
        		if(!node[root].son[sons])
            		node[root].son[sons]=++index;
        		root=node[root].son[sons];
    		}
    		node[root].exist++;
		}
	}trie;
	
	char temp[1000+5],text[500+5];
	int n,ans=0,templen;
	bitset<1000+5> visit[500000+10];//请用bitset作为记忆化数组，否则会爆空间。原因是，bitset是真正地一个“单位”只占1 bit。
	
	void dfs(int ptep,int ptxt)
	{
		if(ptep==templen)
		{
			ans+=trie.node[ptxt].exist;
			trie.node[ptxt].exist=0;
			return;
		}
		
		if(visit[ptxt][ptep])
			return;
		visit[ptxt][ptep]=1;
		
		if(temp[ptep]=='?')
		{
			for(int i=1;i<=4;i++)
				if(trie.node[ptxt].son[i])
					dfs(ptep+1,trie.node[ptxt].son[i]);
		}
		else if(temp[ptep]=='*')
		{
			dfs(ptep+1,ptxt);//空 
			for(int i=1;i<=4;i++)
				if(trie.node[ptxt].son[i])
				{
					dfs(ptep+1,trie.node[ptxt].son[i]);// ?
					dfs(ptep,trie.node[ptxt].son[i]);// ?+* 
				}
		}
		else
		{
			int nxt=getid(temp[ptep]);
			if(trie.node[ptxt].son[nxt])
				dfs(ptep+1,trie.node[ptxt].son[nxt]);
		}
	}
	void yzmain()
	{
		cin>>temp>>n;
		templen=strlen(temp);
		for(int i=1;i<=n;i++)
		{
			cin>>text;
			trie.insert(text);
		}
		dfs(0,0);
		cout<<(n-ans);
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}