【题解】病毒检测

Trie+dfs

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<bitset>
using namespace std;
const int N=500007;
char s[1007];
int len,ans,m;
bitset<1007>vis[N];
struct Tree
{
	int ch[N][10],idx=0,val[N];
	void clear()
	{
		memset(ch,0,sizeof ch);
		idx=0;
	}
	inline int check(char a)
	{
	    if(a=='A') return 1;
		if(a=='G') return 2;
		if(a=='C') return 3;
		if(a=='T') return 4;
		if(a=='?') return 5;
		if(a=='*') return 6;	
	} 
	
	void insert(char s[])
	{
		int p=0;
		
		for(int i=0;i<strlen(s);i++)
		{
			int u=check(s[i]);
			if(!ch[p][u]) ch[p][u]=++idx;
			p=ch[p][u];
		}
		val[p]++;
	}
}Tree;

void dfs(int now,int step)
{
	if(step==len) 
	{
		ans+=Tree.val[now];
		Tree.val[now]=0;
		return;
	}
	if(vis[now][step]) return ;
	vis[now][step]=1;
	int net=Tree.check(s[step]);
	if(net>=1&&net<=4)
	{
		if(Tree.ch[now][net])
		{
			dfs(Tree.ch[now][net],step+1);
		}
		
	}
	if(net==5)
	{
		for(int i=1;i<=4;i++)
		{
			if(Tree.ch[now][i])
			{
				dfs(Tree.ch[now][i],step+1);
			}
		}
	}
	if(net==6)
	{
		dfs(now,step+1);
	    for(int i=1;i<=4;i++)
		{
			if(Tree.ch[now][i])
			{
				dfs(Tree.ch[now][i],step+1);
				dfs(Tree.ch[now][i],step);
			}
		}
	}
}


int main()
{
	cin>>s>>m;
	len=strlen(s);
	Tree.clear();
	for(int i=1;i<=m;i++)
	{
		char ss[1007];
		scanf("%s",ss);
		Tree.insert(ss);
	}
	dfs(0,0);
	printf("%d",m-ans);
	return 0;
}

原文地址：http://www.cnblogs.com/watasky/p/16830050.html