目录

题目描述

思路分析

AC代码

---

题目描述

Trie树又称单词查找树，是一种树形结构，如下图所示。

它是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。

输入的一组单词，创建Trie树。输入字符串，计算以该字符串为公共前缀的单词数。

（提示：树结点有26个指针，指向单词的下一字母结点。）

输入

测试数据有多组

每组测试数据格式为：

第一行：一行单词，单词全小写字母，且单词不会重复，单词的长度不超过10

第二行：测试公共前缀字符串数量t

后跟t行，每行一个字符串

输出

每组测试数据输出格式为：

第一行：创建的Trie树的层次遍历结果

第2~t+1行：对每行字符串，输出树中以该字符串为公共前缀的单词数。

 输入样例

abcd abd bcd efg hig
3
ab
bc
abcde

输出样例

abehbcficddggd
2
1
0 

思路分析

首先是创建单词查找树，创建树前先建结点。因为每个字母的下一个字母都有二十六种可能性，所以结点不光有自己的数据data，还有应该大小为26的指针数组，初始全部为NULL。先把字母a-z放在应该数组里，目的是为了方便给每个字母编号0-25，这样在建树时就可以把next[i]指向新结点了。输出用BFS广度优先遍历。

在统计有几个以该字符串为公共前缀的单词数时，先按照字符串找到对应的结点。把它想成根结点，看它有几个叶节点。我一开始只数了它有几个孩子，但其实每个孩子可能有不止一个孩子，这样最终的答案就不对。用DFS深度优先遍历。

AC代码

#include<iostream>
#include<string>
#include<queue>
using namespace std;
char ch[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};class node{public:char  data;node *next[26];node(){data='6';for(int i=0;i<26;i++)next[i]=NULL;}node(char d){data=d;for(int i=0;i<26;i++)next[i]=NULL;}~node(){}
};
class Tree{public:node *root;Tree(){root=new node();}~Tree(){}void create(string str){node *s=root;int len=str.length();int index;for(int i=0;i<len;i++){char data=str[i];for(int j=0;j<26;j++){if(data==ch[j]) {index=j;}}node *a=new node(data);if(s->next[index]==NULL){s->next[index]=a;s=a;	}else {s=s->next[index];}} }void display(){queue <node*> q;for(int i=0;i<26;i++){if(root->next[i]==NULL) ;else q.push(root->next[i]);}while(!q.empty()){node *s;s=q.front();cout<<q.front()->data;q.pop();for(int i=0;i<26;i++){if(s->next[i]==NULL) ;else q.push(s->next[i]);}}cout<<endl;}int count(string str){node *s=root;int index;int sum=0;int len=str.length();for(int i=0;i<len;i++){char data=str[i];for(int j=0;j<26;j++){if(data==ch[j]) {index=j;}}if(s->next[index]==NULL) return 0;else{s=s->next[index];}}sum=dfs(s);return sum;}int dfs(node *r){int tag=0;int sum=0;for(int i=0;i<26;i++){if(r->next[i]==NULL)  tag++;}if(tag==26) return 1;for(int i=0;i<26;i++){if(r->next[i]!=NULL ) sum+=dfs(r->next[i]);}return sum;} 
};
int main(){string str;Tree myTree;while(cin>>str){myTree.create(str);if(cin.get()=='\n') break;}myTree.display();int t;cin>>t;while(t--){cin>>str;cout<<myTree.count(str)<<endl;}return 0;
}