又称单词查找树，Trie树，前缀树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。
字典树与字典很相似,当你要查一个单词是不是在字典树中,首先看单词的第一个字母是不是在字典的第一层,如果不在,说明字典树里没有该单词,如果在就在该字母的孩子节点里找是不是有单词的第二个字母,没有说明没有该单词,有的话用同样的方法继续查找.字典树不仅可以用来储存字母,也可以储存数字等其它数据。
实战训练：
输入
输入的第一行为一个正整数n，表示词典的大小，其后n行，每一行一个单词（不保证是英文单词，也有可能是火星文单词哦），单词由不超过10个的小写英文字母组成，可能存在相同的单词，此时应将其视作不同的单词。接下来的一行为一个正整数m，表示小Hi询问的次数，其后m行，每一行一个字符串，该字符串由不超过10个的小写英文字母组成，表示小Hi的一个询问。
在20%的数据中n, m<=10，词典的字母表大小<=2.
在60%的数据中n, m<=1000，词典的字母表大小<=5.
在100%的数据中n, m<=100000，词典的字母表大小<=26.
本题按通过的数据量排名哦～
输出
对于小Hi的每一个询问，输出一个整数Ans,表示词典中以小Hi给出的字符串为前缀的单词的个数。
5 babaab babbbaaaa abba aaaaabaa babaababb 5 babb baabaaa bab bb bbabbaab
1 0 3 0 0
代码：
#include <iostream>
#include <vector>
using namespace std;
struct Node {
char val;
int freq;
Node *next[26];
Node(int v, int f): val(v), freq(f) {
int i;
for (i=0; i<26; ++i) {
next[i] = NULL;
}
}
Node():freq(0) {
int i;
for (i=0; i<26; ++i) {
next[i] = NULL;
}
}
};
vector<int> Create(vector<string> &dict, Node *root, vector<string> &str) {
vector<int> res;
int i, len = dict.size(), j;
Node *node;
for (i=0; i<len; ++i) {
node = root;
for (j=0; j<dict[i].size(); ++j) {
if (node->next[dict[i][j]-'a'] == NULL) {
node->next[dict[i][j]-'a'] = new Node(dict[i][j], 1);
}
else {
node->next[dict[i][j]-'a']->freq++;
}
node = node->next[dict[i][j]-'a'];
}
}
for (i=0; i<str.size(); ++i) {
node = root;
for (j=0; j<str[i].size(); ++j) {
if (node->next[str[i][j]-'a'] == NULL) {
break;
}
else {
node = node->next[str[i][j]-'a'];
}
}
if (j == str[i].size()) {
res.push_back(node->freq);
}
else {
res.push_back(0);
}
}
return res;
}
int main() {
vector<string> dict;
vector<string> str;
vector<int> res;
int n,m;
while (cin >> n) {
dict.clear();
str.clear();
res.clear();
dict.resize(n);
int i;
for (i=0; i<n; ++i) {
cin >> dict[i];
}
cin >> m;
str.resize(m);
for (i=0; i<m; ++i) {
cin >> str[i];
}
Node *root = new Node(' ', 0);
res = Create(dict, root, str);
for (i=0; i<res.size(); ++i) {
cout << res[i] << endl;
}
}
return 0;
}