• / 25
  • 下载费用:10 金币  

后缀数组——处理字符串的有力工具.pdf

关 键 词:
后缀数组——处理字符串的有力工具.pdf
资源描述:
I O I 2009国家集训队论文 后缀数组 罗穗骞信息学奥林匹克Ch i n a Nat i o n Ol y mp i ad I n I n f o r mat i c s国家集训队论文题 题 题题目: 目: 目:目:后缀数组 后缀数组 后缀数组后缀数组—— —— ————处理字符串的 有力工具 处理字符串的 有力工具 处理字符串的 有力工具处理字符串的 有力工具作 作 作作者: 者: 者:者:罗穗骞 罗穗骞 罗穗骞罗穗骞指导教师: 指导教师: 指导教师:指导教师:张学东 张学东 张学东张学东学 学 学学校: 校: 校:校:华南师范大学 附属中学 华南师范大学 附属中学 华南师范大学 附属中学华南师范大学 附属中学完成时间: 完成时间: 完成时间:完成时间:20092009年 年 年年11月 月 月月I O I 2009国家集训队论文 后缀数组 罗穗骞2目录摘要 ………………………………………………………………………………… 4关键字 ……………………………………………………………………………… 4正文 ………………………………………………………………………………… 4一、后 缀数组的实现 ………………………………………………………………… 41 . 1 基本定义 ………………………………………………………………… 41 . 2 倍增算法 ………………………………………………………………… 61 . 3 DC3算法 ………………………………………………………………… 91 . 4 倍增算法与 DC3算法的比较 …………………………………………… 1 4二、后缀数组的应用 ……………………………………………………………… 152 . 1 最长公共前缀 …………………………………………………………… 1 5例 1 : 最 长公共前缀 …………………………………………………… 1 72 . 2 单个字符串的相关问题 ………………………………………………… 1 72 . 2 . 1 重复子串 ……………………………………………………… 1 7例 2 : 可 重叠最长重复子串 ……………………………………… 1 7例 3 : 不可 重 叠 最 长 重 复 子 串 ( pku1743) ……………………… … 18例 4 : 可重 叠 的 最 长 重 复 子 串 ( pku3261) ……………………… … 192 . 2 . 2 子串的个数 …………………………………………………… 1 9例 5 : 不相同的子串的个数 ( spoj694,spoj705) ……………… 1 92 . 2 . 3 回文子串 ……………………………………………………… 1 9例 6 : 最长 回 文 子 串 ( ural1297) ………………………………… 192 . 2 . 4 连续重复子串 ………………………………………………… 2 0例 7 : 连 续重复子串 (pku2406)…………………………………… 2 0例 8 : 重 复次数最多的连续重复子串 (spoj687,pku3693)……… 2 12 . 3 两个字符串的相关问题 ………………………………………………… 2 12 . 3 . 1 公共子串 ……………………………………………………… 2 2例 9 : 最 长公共子串 (pku2774,ural1517)……………………… 2 22 . 3 . 2 子串的个数 …………………………………………………… 2 3I O I 2009国家集训队论文 后缀数组 罗穗骞3例 10: 长 度不小于 k 的公共子串的个数 (pku3415)…………… 2 32 . 4 多个字符串的相关问题 ………………………………………………… 2 3例 11:不 小 于 k 个字符串中的最长子串 (pku3294)…………………… 24例 12: 每 个字符串至少出现两次且不重叠的最长子串 (spoj220)…… 2 4例 13: 出 现或反转后出现在每个字符串中的最长子串 (pku3294)…… 2 4三、结束语 ………………………………………………………………………… 253 . 1 总结 ……………………………………………………………………… 2 53 . 2 参考文献 ………………………………………………………………… 2 53 . 3 致谢 ……………………………………………………………………… 2 5I O I 2009国家集训队论文 后缀数组 罗穗骞4后 后 后后缀 缀 缀缀数 数 数数组 组 组组- - - -- - - -处理字符串的 有力工具 处理字符串的 有力工具 处理字符串的 有力工具处理字符串的 有力工具【 【 【【摘要 摘要
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:后缀数组——处理字符串的有力工具.pdf
链接地址:https://www.weizhuannet.com/p-9475321.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开