做法具体而言，把所有字符串转化为带通配符的，然后把 $t$ 全部插进 ACAM 里，然后 $s$ 再一个个查：

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define fir first
#define sec second
#define mkp make_pair 
#define pb push_back
#define lep( i, l, r ) for ( int i = ( l ); i <= ( r ); ++ i )
#define rep( i, r, l ) for ( int i = ( r ); i >= ( l ); -- i )

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;

char _c; bool _f; template < class type > inline void read ( type &x ) {
	_f = 0, x = 0;
	while ( _c = getchar (), !isdigit ( _c ) ) if ( _c == '-' ) _f = 1;
	while ( isdigit ( _c ) ) x = x * 10 + _c - '0', _c = getchar (); if ( _f ) { x = -x; }
}

template < class type > inline void chkmin ( type &x, type y ) { x = ( x <= y ? x : y ); }
template < class type > inline void chkmax ( type &x, type y ) { x = ( x >= y ? x : y ); }

const int N = 2e5 + 5;
const int M = 3e6 + 5;

int n, m;
string s[N];

int idx;

struct Node {
	int ch[27], len, fail, val;
} ac[M];

int res[N], p[M], tail;

int C ( char c ) {
	if ( c == '*' ) {
		return 26;
	}
	return c - 'a';
}

void insert ( int id, string s ) {
	int x = 0;
	for ( int i = 0; i < s.size (); i ++ ) {
		if ( !ac[x].ch[C ( s[i] )] ) {
			ac[x].ch[C ( s[i] )] = ++ idx;
		}
		x = ac[x].ch[C ( s[i] )];
		ac[ac[x].ch[C ( s[i] )]].len = ac[x].len + 1;
	}
	res[id] = x;
}

void get_fail () {
  queue < int > q;
  for ( int i = 0; i < 27; i ++ ) {
    if ( ac[0].ch[i] ) {
      ac[ac[0].ch[i]].fail = 0;
      q.push ( ac[0].ch[i] );
    }
  }
  while ( !q.empty () ) {
    int x = q.front ();
    q.pop ();
		p[tail ++] = x;
    for ( int i = 0; i < 27; i ++ ) {
      if ( ac[x].ch[i] ) {
        ac[ac[x].ch[i]].fail = ac[ac[x].fail].ch[i];
        q.push ( ac[x].ch[i] );
      }
      else {
        ac[x].ch[i] = ac[ac[x].fail].ch[i];
      }
    }
  }
}

void query ( string s ) {
	int x = 0, len = s.size ();
	for ( int i = 0; i < s.size (); i ++ ) {
		x = ac[x].ch[C ( s[i] )];
		for ( ; ac[x].len - 1 > len / 2; x = ac[x].fail ) {
			x = x;
		}
		ac[x].val ++;
	}
}

void Solve () {
	cin >> n >> m;
	for ( int i = 1; i <= n; i ++ ) {
		cin >> s[i];
		s[i] = s[i] + "*" + s[i];
	}
	for ( int i = 1; i <= m; i ++ ) {
		string t;
		cin >> t;
		if ( t[0] == '*' ) {
			t = t.substr ( 1 ) + "*";
		}
		else if ( t[t.size () - 1] == '*' ) {
			t = "*" + t.substr ( 0, t.size () - 1 );
		}
		else {
			for ( int j = 0; j < t.size (); j ++ ) {
				if ( t[j] == '*' ) {
					t = t.substr ( j + 1 ) + "*" + t.substr ( 0, j );
					break;
				}
			}
		}
		insert ( i, t );
	}
	get_fail ();
	for ( int i = 1; i <= n; i ++ ) {
		query ( s[i] );
	}
	while ( tail -- ) {
		ac[ac[p[tail]].fail].val += ac[p[tail]].val;
	}
	for ( int i = 1; i <= m; i ++ ) {
		cout << ac[res[i]].val << '\n';
	}
}

signed main () {
#ifdef judge
	freopen ( "Code.in", "r", stdin );
	freopen ( "Code.out", "w", stdout );
	freopen ( "Code.err", "w", stderr );
#endif
	Solve ();
	return 0;
}