字典树<算法>没尾巴的刺刺鱼

试想一下，你查一个单词比如说book，那么你在字典中，先翻到b开头的部分，在翻到b这一段o开始的部分，依次类推，直到找到book这个单词，如果你不小心看错了一个字母，比如book你看成了boak,那么显然你查找到字母a后，查找不下去了，或者是查找到错误的单词，字典树，就是描述的上述过程。

举个栗子：

六个单词：an,am,and,math,mac,ok那么字典树如下：

每个单词结束时给个标记，比如下面画一个短横线。

树结构来实现

#include#includeusingnamespacestd;structTrie{Trie*next[26];//一个节点只会出现26个字母26种情况intnum;//记录以当前字符串为前缀的单词数量Trie(){for(inti=0;i<26;i++)next[i]=NULL;num=0;}};Trieroot;//根节点voidInsert(charstr[]){//将字符串插入字典树中Trie*p=&root;for(inti=0;str[i];i++){if(p->next[str[i]-'a']==NULL){//如果当前字符没有对应的节点则创建一个p->next[str[i]-'a']=newTrie;//创建一个新的节点}p=p->next[str[i]-'a'];p->num++;}}intFind(charstr[]){//查找以str为前缀的单词数量Trie*p=&root;for(inti=0;str[i];i++){//从第一个字母开始从顶向下依次查找if(p->next[str[i]-'a']==NULL){//如果当前节点没有这个单词中的当前位置的字母则查找失败return0;}p=p->next[str[i]-'a'];}returnp->num;//返回当前单词结尾处的前缀数量}数组实现(更紧凑的代码)

inttrie[10005][26];//数组定义字典树，存储下一个字符的位置intnum[10005]={0};//统计某一个字符串为前缀的数量intpos=1;//当前新分配的存储位置voidInsert(charstr[]){intp=0;for(inti=0;str[i];i++){intn=str[i]-'a';if(trie[p][n]==0){//当前节点没有值trie[p][n]=pos++;//为了在num数组中更好的记录前缀出现的次序}p=trie[p][n];num[p]++;}}intFind(charstr[]){intp=0;for(inti=0;str[i];i++){intn=str[i]-'a';if(trie[p][n]==0){return0;}p=trie[p][n];}returnnum[p];}五，应用查找一组单词中，以某个词为前缀的单词有多少个

intmain(){charstr[11];while(gets(str)){if(!strlen(str))break;//输入空行则跳出去Insert(str);}while(gets(str))cout<

amandokmathmac//输入结束

ma2a2and1c0

注：当然解决该问题，map为一个不错的方法，只需定义mapm将单词插入时，只需要m[str]++即可。