trie树+DFS wa#7~#10

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+5;
string bd;
int n,tot,a[N],ans[N],e;
bool vis[1005][1005];
struct node{
    int nxt[7];
}tree[N];
int idx(char c){
    if(c=='A')return 1;
    if(c=='C')return 2;
    if(c=='T')return 3;
    if(c=='G')return 4;
    if(c=='?')return 5;
    if(c=='*')return 6;
}
void update(string s){
    int cur=0;
    for(int i=0;i<s.size();i++){
        int a=idx(s[i]);
        if(!tree[cur].nxt[a]){
            tree[cur].nxt[a]=++tot;
        }
        cur=tree[cur].nxt[a];
    }
    ans[cur]++;
    return ;
}
void dfs(int cnt,int cur){
    if(cnt==bd.size()){
        e+=ans[cur];
        ans[cur]=0;
        // cout << cur;
        return ;
    }
    if(vis[cnt][cur])return ;
    vis[cnt][cur]=1;
    int x=idx(bd[cnt]);
    if(x>=1&&x<=4){
        if(tree[cur].nxt[x]){
            dfs(cnt+1,tree[cur].nxt[x]);
        }
    }
    if(x==5){
        for(int i=1;i<=4;i++){
            if(tree[cur].nxt[i]){
                dfs(cnt+1,tree[cur].nxt[i]);
            }
        }
    }
    if(x==6){
        dfs(cnt+1,cur);
        for(int i=1;i<=4;i++){
            if(tree[cur].nxt[i]){
                dfs(cnt+1,tree[cur].nxt[i]);
                dfs(cnt,tree[cur].nxt[i]);
            }
        }
    }
}
signed main(){
    cin >> bd >> n;
    for(int i=1;i<=n;i++){
        string s;
        cin >> s;
        update(s);
    }
    dfs(0,0);
    cout << n-e;
    return 0;
}