---
tags: codebook
---
{%hackmd theme-dark %}
# trie

#include<iostream>
#include<vector>
#define _for(n,a) for(int n=0;n!=(a);n++)
using namespace std;
struct trie{
	struct node{
		int cnt;
		vector<node*> next;
		node():cnt(0),next(128,nullptr){}
	};
	node* root;
	void insert(const string& str){
		node* cur=root;
		for(const auto& i:str){
			if(!cur->next[i]) cur->next[i]=new node;
			cur=cur->next[i];
		}
		cur->cnt++;
	}
	int find(const string& str){
		node* cur=root;
		for(const auto& i:str){
			if(!cur->next[i]) return 0;
			cur=cur->next[i];
		}
		return cur->cnt;
	}
	void del(const node* cur){
		if(!cur) return;
		for(int n=0;n!=128;n++)
			del(cur->next[n]);
		delete cur;
	}
	trie():root(new node){}
	trie(const vector<string>& vec):root(new node){for(const auto& i:vec) insert(i);}
	~trie(){del(root);}
};
int main(){
	int r;
	string str;
	cin>>r;
	vector<string> vec(r);
	for(auto& i:vec)
		cin>>i;
	trie t(vec);
	while(cin>>str)
		cout<<t.find(str)<<endl;
	return 0;
}