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

《后缀数组——处理字符串的有力工具》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、IOI2009国家集训队论文后缀数组罗穗骞信息学奥林匹克ChinaNationOlympiadInInformatics国家集训队论文题目：后缀数组——处理字符串的有力工具作者：罗穗骞指导教师：张学东学校：华南师范大学附属中学完成时间：2009年1月IOI2009国家集训队论文后缀数组罗穗骞目录摘要…………………………………………………………………………………4关键字………………………………………………………………………………4正文…………………………………………………………………………………4一、后缀数组的实现…………………………………………………………………41．

2、1基本定义…………………………………………………………………41．2倍增算法…………………………………………………………………61．3DC3算法…………………………………………………………………91．4倍增算法与DC3算法的比较……………………………………………14二、后缀数组的应用………………………………………………………………152．1最长公共前缀……………………………………………………………15例1：最长公共前缀……………………………………………………172．2单个字符串的相关问题…………………………………………………172．2．1重复子串……………………………

3、…………………………17例2：可重叠最长重复子串………………………………………17例3：不可重叠最长重复子串（pku1743）…………………………18例4：可重叠的最长重复子串（pku3261）…………………………192．2．2子串的个数……………………………………………………19例5：不相同的子串的个数（spoj694,spoj705）………………192．2．3回文子串………………………………………………………19例6：最长回文子串（ural1297）…………………………………192．2．4连续重复子串…………………………………………………20例7：连续重复子串(p

4、ku2406)……………………………………20例8：重复次数最多的连续重复子串(spoj687,pku3693)………212．3两个字符串的相关问题…………………………………………………212．3．1公共子串………………………………………………………22例9：最长公共子串(pku2774,ural1517)………………………222．3．2子串的个数……………………………………………………232IOI2009国家集训队论文后缀数组罗穗骞例10：长度不小于k的公共子串的个数(pku3415)……………232．4多个字符串的相关问题…………………………………………………23

5、例11：不小于k个字符串中的最长子串(pku3294)……………………24例12：每个字符串至少出现两次且不重叠的最长子串(spoj220)……24例13：出现或反转后出现在每个字符串中的最长子串(pku3294)……24三、结束语…………………………………………………………………………253．1总结………………………………………………………………………253．2参考文献…………………………………………………………………253．3致谢………………………………………………………………………253IOI2009国家集训队论文后缀数组罗穗骞后缀数组----处理字符串的有力工

6、具【摘要】后缀数组是处理字符串的有力工具。后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也并不逊色，而且它比后缀树所占用的内存空间小很多。可以说，在信息学竞赛中后缀数组比后缀树要更为实用。本文分两部分。第一部分介绍两种构造后缀数组的方法，重点介绍如何用简洁高效的代码实现，并对两种算法进行了比较。第二部分介绍后缀数组在各种类型题目中的具体应用。【关键字】字符串后缀后缀数组名次数组基数排序【正文】一、后缀数组的实现本节主要介绍了后缀数组的两种实现方法：倍增算法和DC3算法，并对两种算法进行了比较。可能有的读者会认为这两

7、种算法难以理解，即使理解了也难以用程序实现。本节针对这个问题，在介绍这两种算法的基础上，还给出了简洁高效的代码。其中倍增算法只有25行，DC3算法只有40行。１．１基本定义子串：字符串S的子串r[i..j]，i≤j，表示r串中从i到j这一段，也就是顺次排列r[i],r[i+1],...,r[j]形成的字符串。后缀：后缀是指从某个位置i开始到整个串末尾结束的一个特殊子串。字4IOI2009国家集训队论文后缀数组罗穗骞符串r的从第i个字符开始的后缀表示为Suffix(i)，也就是Suffix(i)=r[i..len(r)]。大小比较：关于字符串的大小比较