病毒检测

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1123456;
int n, ans;
string s;
string p;
queue<int> qt; // 在 tr 上走到的位置
queue<int> qp; // 在 p 上走到的位置
int c2i[256];
bitset<1005> vis[MAXN];
struct Trie
{
    int tr[MAXN][5], tot; //根节点为 0
    int cnt[MAXN];
    void insert(string &s)
    {
        int u = 0;
        for (int i = 0; i < s.length(); i++)
        {
            if (!tr[u][c2i[s[i]]])
                tr[u][c2i[s[i]]] = ++tot;
            u = tr[u][c2i[s[i]]];
        }
        cnt[u]++;
    }
} tr;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    c2i['A'] = 0, c2i['C'] = 1, c2i['T'] = 2, c2i['G'] = 3;
    cin >> p;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> s;
        tr.insert(s);
    }
    /*
    for (int i = 0; i <= tr.tot; i++)
    {
        cout << i << " " << tr.cnt[i] << ":"
             << tr.tr[i]['A' - 'A'] << " "
             << tr.tr[i]['C' - 'A'] << " "
             << tr.tr[i]['T' - 'A'] << " "
             << tr.tr[i]['G' - 'A'] << "\n";
    }
    */
    qt.push(0);
    qp.push(0);
    while (!qt.empty())
    {
        int nowT = qt.front();
        qt.pop();
        int nowP = qp.front();
        qp.pop();
        if (nowP == p.length())
        {
            ans += tr.cnt[nowT];
            tr.cnt[nowT] = 0;
            // cout << nowT << " : " << ans << "\n";
            continue;
        }
        if (p[nowP] == 'A' || p[nowP] == 'C' || p[nowP] == 'T' || p[nowP] == 'G')
        {
            if (tr.tr[nowT][c2i[p[nowP]]] && !vis[tr.tr[nowT][c2i[p[nowP]]]][nowP + 1])
            {
                vis[tr.tr[nowT][c2i[p[nowP]]]][nowP + 1] = true;
                qt.push(tr.tr[nowT][c2i[p[nowP]]]);
                qp.push(nowP + 1);
            }
        }
        else if (p[nowP] == '?')
        {
            for (int i = 0; i < 4; i++)
                if (tr.tr[nowT][i] && !vis[tr.tr[nowT][i]][nowP + 1])
                {
                    vis[tr.tr[nowT][i]][nowP + 1] = true;
                    qt.push(tr.tr[nowT][i]);
                    qp.push(nowP + 1);
                }
        }
        else if (p[nowP] == '*')
        {
            for (int i = 0; i < 4; i++)
                if (tr.tr[nowT][i] && !vis[tr.tr[nowT][i]][nowP])
                {
                    vis[tr.tr[nowT][i]][nowP] = true;
                    qt.push(tr.tr[nowT][i]);
                    qp.push(nowP);
                }
            if (p[nowP] == '*' && !vis[nowT][nowP + 1])
            {
                vis[nowT][nowP + 1] = true;
                qt.push(nowT);
                qp.push(nowP + 1);
            }
        }
    }
    cout << n - ans << "\n";
    return 0;
}