Dictionary tree template

Ignatius I've had a problem recently , The teacher gave him a lot of words ( Only lowercase letters , There will be no repetition of words ), Now the teacher asked him to count the number of words prefixed with a string ( Words themselves are prefixes of their own ).

Input

The first part of the input data is a word list , One word per line , The length of a word does not exceed 10, They represent what teachers give to Ignatius Statistical words , An empty line represents the end of the word list . The second part is a series of questions , One question per line , Every question is a string .

Be careful : There is only one set of test data , Processing to the end of the file .

Output

For each question , Give the number of words prefixed with the string .

Sample

banana band bee absolute acm ba b band abc 

2 3 1 0 

#include<iostream>
#include<math.h>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
const int maxn = 1e6 + 10;
int tree[maxn][30];
ll sum[maxn];
bool flag[maxn];

int tot;
void build_tree(char* s) {
	int root = 0;
	int id;
	int len = strlen(s);
	for (int i = 0; i < len; i++) {
		id = s[i] - 'a';
		if (!tree[root][id])tree[root][id] = ++tot;
		sum[tree[root][id]]++;// Every time a word comes here, add one , You can know how many words there are after 
		root = tree[root][id];
	}
	flag[root] = true;
}
ll find(char* s) {
	int root = 0;
	int id;
	ll res = 0;
	int len = strlen(s);
	for (int i = 0; i < len; i++) {
		id = s[i] - 'a';
		if (!tree[root][id])return 0;
		root = tree[root][id];
	}
	return sum[root];
}
char s[maxn];
int main() {

	while (gets(s)) {

		if (s[0] == '\0')break;
		build_tree(s);
	}

	while (cin >> s) {

		cout << find(s) << endl;
	}
	return 0;
}