传送门
我也没想到map如此垃圾，bitset优秀啊
直接trie树上搜索就好了
代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<bitset>
#include<queue>
using namespace std;
void read(int &x) {
char ch; bool ok;
for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;
}
#define rg register
const int maxn=1010,mod=1e4;
struct oo{int x;short y;};queue<oo>q;bitset<maxn>mp[250010];bool ed[250010];
int n,m,rt=1,id=1,ch[250010][5];char s[maxn],ss[510];short w[500],ans;
void insert(char *s,int d)
{
int len=strlen(s+1);rt=1;
for(rg int i=1;i<=len;i++)
{
int now=w[s[i]];
if(!ch[rt][now])ch[rt][now]=++id;
rt=ch[rt][now];
}
ed[rt]=1;
}
void bfs()
{
q.push((oo){1,0});mp[1][0]=1;
while(!q.empty())
{
oo x=q.front();q.pop();
if(ed[x.x]&&x.y==m){ans++;continue;}
if(w[s[x.y+1]]&&ch[x.x][w[s[x.y+1]]]&&!mp[ch[x.x][w[s[x.y+1]]]][x.y+1]){q.push((oo){ch[x.x][w[s[x.y+1]]],x.y+1}),mp[ch[x.x][w[s[x.y+1]]]][x.y+1]=1;continue;}
if(s[x.y+1]=='?')for(rg int i=1;i<=4;i++){if(ch[x.x][i]&&!mp[ch[x.x][i]][x.y+1])q.push((oo){ch[x.x][i],x.y+1}),mp[ch[x.x][i]][x.y+1]=1;}
if(s[x.y+1]=='*')
{
for(rg int i=1;i<=4;i++)if(ch[x.x][i]&&!mp[ch[x.x][i]][x.y])q.push((oo){ch[x.x][i],x.y}),mp[ch[x.x][i]][x.y]=1;
if(!mp[x.x][x.y+1])q.push((oo){x.x,x.y+1}),mp[x.x][x.y+1]=1;
}
}
}
int main()
{
scanf("%s",s+1),m=strlen(s+1),read(n);w['A']=1,w['G']=2,w['C']=3,w['T']=4;
for(rg int i=1;i<=n;i++)scanf("%s",ss+1),insert(ss,i);
bfs();printf("%d
",n-ans);
}