ACM-字典树详解

ACM程序设计杭州电子科技大学刘春英[e-mail]集训队讲座（二）字典树（Trie）导引问题(HDOJ-1251)Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).初步分析（Brute-force）Question:如果单词表容量很大-查找效率?-低更有效率的方法：字典树假设单词表容量为M，需要统计的前缀数量为N，单词的平均长度为L，则常规算法的时间复杂度是？什么是字典树？字典树：又称为Trie，是一种用于快速检索的多叉树结构。Trie把要查找的关键词看作一个字符序列，并根据构成关键词字符的先后顺序构造用于检索的树结构；一棵m度的Trie树或者为空，或者由m棵m度的Trie树构成。特别地：和二叉查找树不同，在Trie树中，每个结点上并非存储一个元素。Trie的图示特点：利用串的公共前缀-节约内存根结点不包含任何字母其余结点仅包含一个字母(非元素)每个结点的子节点包含字母不同Trie的查找（最主要的操作）(1)在trie树上进行检索总是始于根结点。(2)取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索。(3)在(5)在某个结点处，关相应的子树上，取得要查找关键词的第二个字母，并进一步选择对应的子树进行检索。(4)...键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。Trie的数据结构定义structdictree{dictree*child[26];intn;//根据需要变化};dictree*root;查找效率分析在trie树中查找一个关键字的时间和树中包含的结点数无关，而取决于组成关键字的字符数。（对比：二叉查找树的查找时间和树中的结点数有关O(log2n)。）如果要查找的关键字可以分解成字符序列且不是很长，利用trie树查找速度优于二叉查找树。若关键字长度最大是5，则利用trie树，利用5次比较可以从265＝11881376个可能的关键字中检索出指定的关键字。而利用二叉查找树至少要进行log2265=23.5次比较。示例—(HDOJ-1075)WhatAreYouTalkingAbout题目描述：IgnatiusissoluckythathemetaMartianyesterday.Buthedidn'tknowthelanguagetheMartiansuse.TheMartiangiveshimahistorybookofMarsandadictionarywhenitleaves.NowIgnatiuswanttotranslatethehistorybookintoEnglish.Canyouhelphim?样本数据(HDOJ-1075)SampleInputSTARTfromfiwohellodifhmarsriwosfearthfnnvklikefiiwjENDSTARTdifh,i'mfiworiwosf.ifiiwjfnnvk!ENDSampleOutputhello,i'mfrommars.ilikeearth!InputDescription:Allthewordsareinthelowercase,andeachwordwillcontainatmost10characters,andeachlinewillcontainatmost3000characters.题目分析(HDOJ-1075)特点？数据量大主要任务？查找单词解决方法？字典树字典树结构（除指针）？单词信息（英文）额外提醒？字符串操作的熟练应用其他问题？NO~相关练习HDOJ-1075WhatAreYouTalkingAboutHDOJ-1251统计难题HDOJ-1298T9HDOJ-1800FlyingtotheMarsZOJ-1109LanguageofFatMouse附:参考源码(HDOJ-1251)#includestdio.h#includestring.h#includestdlib.hstructdictree{structdictree*child[26];intn;};structdictree*root;voidinsert(char*source){intlen,i,j;structdictree*current,*newnode;len=strlen(source);if(len==0)return;current=root;for(i=0;ilen;i++){if(current-child[source[i]-'a']!=0){current=current-child[source[i]-'a'];current-n=current-n+1;}else{newnode=(structdictree*)malloc(sizeof(structdictree));for(j=0;j26;j++)newnode-child[j]=0;current-child[source[i]-'a']=newnode;current=newnode;current-n=1;}}}intfind(char*source){inti,len;structdictree*current;len=strlen(source);if(len==0)return0;current=root;for(i=0;ilen;i++){if(current-child[source[i]-'a']!=0)current=current-child[source[i]-'a'];elsereturn0;}returncurrent-n;}intmain(){chartemp[11];inti,j;root=(structdictree*)malloc(sizeof(structdictree));for(i=0;i26;i++)root-child[i]=0;root-n=2;while(gets(temp),strcmp(temp,)!=0)insert(temp);while(scanf(%s,temp)!=EOF){i=find(temp);printf(%d\n,i);}}下一讲～WelcometoHDOJThankYou~