#include #include #include #include #include #include struct node { bool isLeaf {false}; node* sons[10] {nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr}; }; int N; int Q; std::vector undamaged; node* trie; int num_to_i(char n) { return n - '0'; } node* mk_trie() { node* root = new node(); for (const std::string& num : undamaged) { node* curr = root; for (int numpos = 0; numpos < 9; ++numpos) { int i = num_to_i(num[numpos]); if (! curr->sons[i]) { curr->sons[i] = new node(); } curr = curr->sons[i]; } curr->isLeaf = true; } return root; } int may_correspond_count(const std::string& ns, int npos, node* pos) { if (pos->isLeaf) { return 1; } char c = ns[npos]; if (c == '?') // coffee { int res = 0; for (int k = 0; k < 9; ++k) { if (pos->sons[k]) { res += may_correspond_count(ns, npos + 1, pos->sons[k]); } } return res; } else { int i = num_to_i(c); if (! pos->sons[i]) { return 0; } return may_correspond_count(ns, npos + 1, pos->sons[i]); } } std::string preprocess(const std::string& line) { auto it = std::find(begin(line), end(line), '*'); if (it == end(line)) { return line; } int pos = std::distance(begin(line), it); std::string head = line.substr(0, pos); std::string tail = line.substr(pos + 1); std::string glue(9 - (line.size() - 1), '?'); return head + glue + tail; } int main() { std::cin >> N; undamaged.reserve(N); for (int k = 0; k < N; ++k) { std::string line; std::cin >> line; undamaged.emplace_back(std::move(line)); } trie = mk_trie(); std::cin >> Q; for (int k = 0; k < Q; ++k) { std::string line; std::cin >> line; line = preprocess(line); std::cout << may_correspond_count(line, 0, trie) << std::endl; } return 0; }