RT，WA on #7~#10。

Code:

#include<bits/stdc++.h>
using namespace std;

string s,ss;
int n,m;

int h[150];

void init_h(){
    h['A']=0;
    h['G']=1;
    h['T']=2;
    h['C']=3;
}

int trie[250005][4],ep[250005];

void Insert(string x){
    static int cnt=1;
    int p=1;

    for(int i=0;i<x.size();i++){
        if(!trie[p][h[x[i]]]){
            cnt++;
            trie[p][h[x[i]]]=cnt;
        }

        p=trie[p][h[x[i]]];
    }

    ep[p]++;
}

int ans;

bitset<1005>vis[250005];

void dfs(int step,int p){
    if(vis[step][p])
        return;
    
    if(step==n){
        ans+=ep[p];

        ep[p]=0;
        return;
    }

    vis[step][p]=1;

    switch(s[step]){
        case 'A':
        case 'G':
        case 'T':
        case 'C':{
            if(trie[p][h[s[step]]])
                dfs(step+1,trie[p][h[s[step]]]);
            break;
        }
        case '?':{
            for(int i=0;i<4;i++)
                if(trie[p][i])
                    dfs(step+1,trie[p][i]);
            break;
        }
        case '*':{
            dfs(step+1,p);
            
            for(int i=0;i<4;i++)
                if(trie[p][i]){
                    dfs(step+1,trie[p][i]);
                    dfs(step,trie[p][i]);
                }
            break;
        }
    }
}

int main(){
    init_h();

    cin>>s>>m;
    n=s.size();
    
    for(int i=1;i<=m;i++){
        cin>>ss;
        Insert(ss);
    }
    
    dfs(0,1);

    cout<<m-ans;
    return 0;
}