欢迎访问~原文出处——

---

---

题意概括

　　现在有一些串和一个病毒模板。让你统计非病毒串的总数。串个数<=500。

　　串由'A' 'C' 'G' 'T'构成，长度<=500。

　　病毒模板（长度<=1000）较为复杂，由'A' 'C' 'G' 'T' '*' '?'组成。其中'A' 'C' 'G' 'T'没有特异功能。但是'*' 和 '?'有特意功能：

　　'*'：在这里可以填充任意长度的任意串（由A,C,G,T组成，长度可以为0）。

　　'?'：在这里能且仅能填一个字母，这个字母在A,C,G,T中选。

　　如果病毒模板通过在'.'和'?'中填字母可以做到和某一个串相同，那么这个串就是病毒串。反之就是非病毒串。

---

题解

　　我们发现连续的'*'是没用的可以压成一个'*'，花几行代码压掉。

　　然后对于每一个串，我们跑一个二维的dp。

　　用f[i][j]表示从病毒串的第i位开始，当前串的第j位开始，能否得到匹配。

　　那么有3种转移：

　　1. 当前模板位为‘*’，那么我们可以考虑结束'*'或者继续匹配当前串，故f[i][j]=f[i][j+1] or f[i+1][j]

　　2. 当前模板位为'?'，那么我们只能做到和当前字符匹配，故f[i][j]=f[i+1][j+1]

　　3. 当前模板位为字符，那么我判断一下和当前串位是否相同，如果不同那么f[i][j]=0，否则f[i][j]=f[i+1][j+1]

　　注意特殊情况：

　　最后的时候，模板串还有'*',但是当前串已经匹配完的情况要注意一下。

　　dp主体写在dfs里面。

---

代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int M=1005,N=505;int t,n,m,ans=0,f[M][N];char str[M],ch[N];void recreate(){	int m_=1;	for (int i=2;i<=m;i++)		if (!(str[i]==str[i-1]&&str[i]=='*'))			str[++m_]=str[i];	m=m_;}bool dfs(int x,int y){	if (~f[x][y])		return f[x][y];	if (x>m&&y>n)		return f[x][y]=1;	if (str[x]=='*'&&y>n)		return f[x][y]=dfs(x+1,y);	if (x>m||y>n)		return f[x][y]=0;	if (str[x]=='?')		return f[x][y]=dfs(x+1,y+1);	if (str[x]=='*')		return f[x][y]=dfs(x,y+1)||dfs(x+1,y);	if (str[x]!=ch[y])		return f[x][y]=0;	return f[x][y]=dfs(x+1,y+1);}int main(){	scanf("%s",str+1);	m=strlen(str+1);	recreate();	scanf("%d",&t);	for (int i=1;i<=t;i++){		scanf("%s",ch+1);		n=strlen(ch+1);		memset(f,-1,sizeof f);		if (!dfs(1,1))			ans++;	}	printf("%d",ans);	return 0;}