题目描述
Trie树又称单词查找树，是一种树形结构，如下图所示。
它是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。
输入的一组单词，创建Trie树。输入字符串，计算以该字符串为公共前缀的单词数。
（提示：树结点有26个指针，指向单词的下一字母结点。）
输入
测试数据有多组
每组测试数据格式为：
第一行：一行单词，单词全小写字母，且单词不会重复，单词的长度不超过10
第二行：测试公共前缀字符串数量t
后跟t行，每行一个字符串
输出
每组测试数据输出格式为：
第一行：创建的Trie树的层次遍历结果
第2~t 1行：对每行字符串，输出树中以该字符串为公共前缀的单词数。
输入样例1
abcd abd bcd efg hig 3 ab bc abcde
输出样例1
abehbcficddggd 2 1 0
AC代码
代码语言：javascript复制#include<iostream>
#include<sstream>
#include<vector>
#include<queue>
using namespace std;
struct Node{
Node*next[26]={NULL};
};
class Trie{
Node*root=new Node;
public:
Trie(){
string data;
getline(cin, data);
stringstream turn(data);
while(turn >> data){
int i=0;
Node*current=root;
while(i<data.size()&¤t->next[data[i]-'a']){
current=current->next[data[i]-'a'];
i ;
}
for(;i<data.size();i ){
Node*newOne=new Node;
current=current->next[data[i]-'a']=newOne;
}
}
BFS();
int t;
cin>>t;
while(t--){
cin>>data;
Find(data);
}
}
void BFS(){
queue<Node*>open;
open.push(root);
while(!open.empty()){
Node*current=open.front();
open.pop();
for(int i=0;i<26;i )
if(current->next[i]){
cout<<char(i 'a');
open.push(current->next[i]);
}
}
cout<<endl;
}
void DFS(Node*current,int&count){
bool leave=true;
for(int i=0;i<26;i )
if(current->next[i]){
leave= false;
break;
}
if(leave){
count ;
return;
}
for(int i=0;i<26;i )
if(current->next[i])
DFS(current->next[i],count);
}
void Find(string&data){
Node*current=root;
int i=0,count=0;
while(i<data.size()&¤t->next[data[i]-'a']){
current=current->next[data[i]-'a'];
i ;
}
if(i==data.size()){
for(int j=0;j<26;j )
if(current->next[j])
DFS(current->next[j],count);
cout<<count<<endl;
}else cout<<'0'<<endl;
}
};
int main() {
Trie test;
return 0;
}
