建立Trie树，输出前缀单词个数。
#include <iostream>
#include <vector>
using namespace std;
struct node {
char value;
int times;
node* sons[26];
node(char a) {
value = a;
times = 1;
for(int i = 0; i < 26; i++)
sons[i] = NULL;
}
};
node* root;
void insert_words(string s) {
node* now = root;
for(int i = 0; i < s.size() ;i++) {
node* t = now->sons[s[i] - 'a'];
if(t != NULL) {
t->times++;
now = t;
}
else {
t = new node(s[i]);
now->sons[s[i] - 'a'] = t;
now = t;
}
}
}
int query_times(string s) {
node* now = root;
for(int i = 0; i < s.size() ;i++) {
node* t = now->sons[s[i] - 'a'];
if(t != NULL) {
now = t;
}
else
return 0;
}
return now->times;
}
int main()
{
int n, m;
string inputstr;
cin >> n;
root = new node('0');
for(int i = 0; i < n; i++) {
cin >> inputstr;
insert_words(inputstr);
}
cin >> m;
for(int i = 0; i < m; i++) {
cin >> inputstr;
cout << query_times(inputstr) <<endl;
}
return 0;
}
