《ACM-字典树详解ppt课件.ppt》由会员分享，可在线阅读，更多相关《ACM-字典树详解ppt课件.ppt（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、ACM程序设计程序设计杭州电子科技大学 刘春英集训队讲座（二）集训队讲座（二）字典树字典树（Trie）导引问题导引问题(HDOJ-1251)Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).初步分析初步分析（Brute-force）Question:如果单词表容量很大-查找效率?-低更有效率的方法：字典树 假设单词表容量为M，需要统计的前缀数量为N，单词的平均长度为L，则常规算法的时间复杂度是？什么是字典树？什么是字典树？字典树字典树：又称为Trie，是一种用于快速检索的多叉
2、树结构。Trie把要查找的关键词看作一个字符序列，并根据构成关键词字符的先后顺序构造用于检索的树结构；一棵m度的Trie树或者为空，或者由m棵m度的Trie树构成。特别地：和二叉查找树不同，在Trie树中，每个结点上并非存储一个元素。Trie的图示的图示特点：特点：n利用串的公共前缀-节约内存n根结点不包含任何字母n其余结点仅包含一个字母(非元素)n每个结点的子节点包含字母不同Trie的查找（最主要的操作）的查找（最主要的操作）(1)在trie树上进行检索总是始于根结点总是始于根结点。(2)取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索。(3)在(5)在某个结
3、点处，关相应的子树上，取得要查找关键词的第二个字母，并进一步选择对应的子树进行检索。(4).键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。Trie的数据结构定义的数据结构定义nstruct dictree n n dictree*child26;n int n;/根据需要变化n;n dictree*root;查找效率分析查找效率分析n在trie树中查找一个关键字的时间和树中包含的结点数无关，而取决于组成关键字的字符数。（对比：二叉查找树的查找时间和树中的结点数有关O(log2n)。）n如果要查找的关键字可以分解成字符序列且不是很长，利用trie树查找速度优于二叉查找树。n若关键
4、字长度最大是5，则利用trie树，利用5次比较可以从26511881376个可能的关键字中检索出指定的关键字。而利用二叉查找树至少要进行log2265=23.5次比较。示例示例(HDOJ-1075)What Are You Talking About 题目描述：题目描述：Ignatius is so lucky that he met a Martian yesterday.But he didnt know the language the Martians use.The Martian gives him a history book of Mars and a dictionary w
5、hen it leaves.Now Ignatius want to translate the history book into English.Can you help him?样本数据样本数据(HDOJ-1075)Sample InputSTART from fiwo hello difh mars riwosf earth fnnvk like fiiwj END START difh,im fiwo riwosf.i fiiwj fnnvk!END Sample Outputhello,im from mars.i like earth!nInput Description:All
6、 the words are in the lowercase,and each word will contain at most 10 characters,and each line will contain at most 3000 characters.题目分析题目分析(HDOJ-1075)n特点？数据量大n主要任务？查找单词n解决方法？字典树n字典树结构（除指针）？单词信息（英文）n额外提醒？字符串操作的熟练应用n其他问题？NO相关练习相关练习nHDOJ-1075What Are You Talking About nHDOJ-1251统计难题 nHDOJ-1298T9 nHDOJ
7、-1800 Flying to the Mars nZOJ-1109 Language of FatMouse 附附:参考源码参考源码(HDOJ-1251)n#include stdio.h n#include string.h n#include stdlib.h nstruct dictree n n struct dictree*child26;n int n;n;nstruct dictree*root;nvoid insert(char*source)n n int len,i,j;n struct dictree*current,*newnode;n len=strlen(sour
8、ce);n if(len=0)return;n current=root;n for(i=0;ichildsourcei-a!=0)n n current=current-childsourcei-a;n current-n=current-n+1;n n else n n newnode=(struct dictree*)malloc(sizeof(struct dictree);n for(j=0;jchildj=0;n current-childsourcei-a=newnode;n current=newnode;n current-n=1;n n n nint find(char*s
9、ource)n n int i,len;n struct dictree*current;n len=strlen(source);n if(len=0)return 0;n current=root;n for(i=0;ichildsourcei-a!=0)n current=current-childsourcei-a;n else return 0;n n return current-n;n nint main()nn char temp11;n int i,j;n root=(struct dictree*)malloc(sizeof(struct dictree);n for(i=0;ichildi=0;n root-n=2;n while(gets(temp),strcmp(temp,)!=0)n insert(temp);n while(scanf(%s,temp)!=EOF)n n i=find(temp);n printf(%dn,i);n n下一讲下一讲Welcome to HDOJWelcome to HDOJThank Thank You You