国家集训队2009论文集thesis

《国家集训队2009论文集thesis》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、浅析字母树在信息学竞赛中的应用浙江省绍兴市第一中学董华星2009年1月资源管理器检索单纯枚举简单易写效率低下字母树字母树相关概念CBASIINICASRootP串的公共前缀↓节约存储内存↓加快检索字母树的应用1.在快速检索中的应用2.在“串”排序方面的应用3.在减少无效转移方面的应用4.在最长公共前缀问题上的应用5.在多模式串匹配问题上的应用字母树在“串”排序方面的应用例请你将下列名字按字典序排序并输出ReaganBushClintonBushObama……字母树在“串”排序方面的应用RootBabOCmalin

2、tonushReagan线性例给出有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用时字母树用时100010001020ms20ms11111

3、1112030ms20ms125012503030ms20ms142814284030ms20ms166616665030ms30ms200020006050ms20ms250025007060ms30ms333333338090ms20ms5000500090170ms60ms1000010000100560ms90ms字母树在减少无效转移方面的应用字母树在最长公共前缀问题的应用最长公共前缀字母树最近公共祖先字母树在最长公共前缀问题的应用例两个实数都保留小数点后k位，若两数一致，则k为它们的公共精度。其中，最大的

4、k叫做它们的最长公共精度。现在，有N个不足1的非负实数，让你求出一个数字x，使得x和所有数字的最长公共精度之和最大。字母树在最长公共前缀问题的应用0.3150.310.3140.33115Root4简单快捷高效311字母树的局限时间空间←字符集做题前需合理分析金无足赤人无完人好懂好想好写好用基本的查找排序减少无效转移最长公共前缀AC自动机总结检索感谢时刻关心我的亲人和辛勤培育我的老师。感谢鼓励并帮助我的各位朋友。感谢给我这次表现机会的中国计算机学会和IOI2009中国国家集训队教练。感谢各位观众。感谢祝大家学习愉快

5、，生活幸福！欢迎大家的指点与提问！最后