浅析字母树在信息学竞赛中应用thesis.pptx

浅析字母树

在信息学竞赛中的应用浙江省绍兴市第一中学董华星2009年1月

资源管理器检索单纯枚举简单易写效率低下字母树？

字母树相关概念CBASIINICASRootP串的公共前缀↓节约存储内存↓加快检索

字母树的应用1.在快速检索中的应用2.在“串”排序方面的应用3.在减少无效转移方面的应用4.在最长公共前缀问题上的应用5.在多模式串匹配问题上的应用

字母树在“串”排序方面的应用例请你将下列名字按字典序排序并输出ReaganBushClintonBushObama……

字母树在“串”排序方面的应用RootBabOCmalintonushReagan线性

例给出有N个单词的字典，和一篇长L的无符号文章。问这文章有多少种解释方式。T[i+1..i+x]是单词则F[i+x]+=F[i]最后答案即为F[L]字母树在减少无效转移方面的应用递推？

1.单纯枚举2.KMP算法3.字母树字母树在减少无效转移方面的应用T[i+1..i+x]是单词则F[i+x]+=F[i]

字母树在减少无效转移方面的应用3.字母树acbadacbadacbadRootadabcacbad

单词数N文章长L单词最长lKMP用时字母树用时100010001020ms20ms111111112030ms20ms125012503030ms20ms142814284030ms20ms166616665030ms30ms200020006050ms20ms250025007060ms30ms333333338090ms20ms5000500090170ms60ms1000010000100560ms90ms字母树在减少无效转移方面的应用

字母树在最长公共前缀问题的应用最长公共前缀字母树最近公共祖先

字母树在最长公共前缀问题的应用例两个实数都保留小数点后k位，若两数一致，则k为它们的公共精度。其中，最大的k叫做它们的最长公共精度。现在，有N个不足1的非负实数，让你求出一个数字x，使得x和所有数字的最长公共精度之和最大。

字母树在最长公共前缀问题的应用0.3150.310.3140.33115Root4简单快捷高效311

字母树的局限时间空间←字符集做题前需合理分析金无足赤人无完人

好懂好想好写好用基本的查找排序减少无效转移最长公共前缀AC自动机总结检索

感谢时刻关心我的亲人和辛勤培育我的老师。感谢鼓励并帮助我的各位朋友。感谢给我这次表现机会的中国计算机学会和IOI2009中国国家集训队教练。感谢各位观众。感谢祝大家学习愉快，生活幸福！欢迎大家的指点与提问！最后