rt,记搜+trie

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const ll M=500005;
ll pb(char c)
{
	ll p;
	switch(c)
	{
		case 'A':p=0;break;
		case 'C':p=1;break;
		case 'T':p=2;break;
		case 'G':p=3;break;
		case '*':p=4;break;
		case '?':p=5;break;
	}
	return p;
}
struct trie
{
	ll t[M][4],cnt,real[M];
	void insert(string s,int l)
	{
		ll p=0;
		for(int i=0;i<l;i++)
		{
			ll c=pb(s[i]);
			if(!t[p][c]) t[p][c]=++cnt;
			p=t[p][c];
		}
		real[p]++;
	}
}t;
string vs,x;
ll n,m,ans;
bitset<1005>f[M];
void dfs(ll k,ll p)
{
	if(k==m+1)
	{
		ans+=t.real[p];
		t.real[p]=0;
		return;
	}
	if(f[k][p])
	{
		return;
	}
	f[k][p]=1;
	ll x=pb(vs[k]);
	if(x>=0&&x<=3)
	{
		if(t.t[p][x])
		{
			dfs(k+1,t.t[p][x]);
		}
	}
	else if(x==4)
	{
		for(int i=0;i<4;i++)
		{
			if(t.t[p][i])
			{
				dfs(k+1,t.t[p][i]);
			}
		}
	}
	else
	{
		dfs(k+1,p);
		for(int i=0;i<4;i++)
		{
			if(t.t[p][i])
			{
				dfs(k+1,t.t[p][i]);
				dfs(k,t.t[p][i]);
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>vs;
	m=vs.size();
	vs=' '+vs;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		t.insert(x,x.size());
	}
	dfs(1,0);
	cout<<n-ans;
	return 0;
}