国家集训队2009论文集后缀数组——处理字符

《国家集训队2009论文集后缀数组——处理字符》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、处理字符串的有力工具---华南师范大学附属中学罗穗骞指导教师：张学东后缀数组目录第一部分后缀数组的实现DC3算法第二部分后缀数组的应用例1:求两个字符串的最长公共子串基本定义【后缀数组SA】后缀数组保存的是一个字符串的所有后缀的排序结果。其中SA[i]保存的是字符串所有的后缀中第i小的后缀的开头位置。【名次数组Rank】名次数组Rank[i]保存的是后缀i在所有后缀中从小到大排列的“名次”。为了叙述方便，以第k个字符开始的后缀称为后缀k。基本定义以字符串“aabaaaab”为例。DC3算法复杂难以实现仅40行代码DC3算法（1）、先将后缀分成两部分，然后对第一部分的后缀排

2、序。（2）、利用（1）的结果，对第二部分的后缀排序。（3）、将（1）和（2）的结果合并，即完成对所有后缀排序。（1）、将后缀分成两部分字符的编号从0开始。将后缀分成两部分：第一部分是后缀k（k模3不等于0）第二部分是后缀k（k模3等于0）对第一部分的后缀排序。为了方便接下来的操作，这里要求字符串必须以一个最小的字符结尾。suffix(1)suffix(2)递归后缀数组步骤（1）完成DC3算法（1）、先将后缀分成两部分，然后对第一部分的后缀排序。（2）、利用（1）的结果，对第二部分的后缀排序。（3）、将（1）和（2）的结果合并，即完成对所有后缀排序。（2）、对第二部分的后缀

3、排序第一关键字第二关键字基数排序即可步骤（2）完成DC3算法（1）、先将后缀分成两部分，然后对第一部分的后缀排序。（2）、利用（1）的结果，对第二部分的后缀排序。（3）、将（1）和（2）的结果合并，即完成对所有后缀排序。（3）、将(1)和(2)的结果合并每次的比较都可以高效的完成步骤（3）完成算法分析假设这个算法的时间复杂度为f(n)。第（1）步排序的时间为O(n)（一般来说，m比较小，这里忽略不计）,新的字符串的长度不超过2n/3，求新字符串的sa的时间为f(2n/3)。第（2）和第（3）步的时间都是O(n)。算法分析f(n)=O(n)+f(2n/3)f(n)≤c×n+

4、f(2n/3)f(n)≤c×n+c×(2n/3)+c×(4n/9)+……≤3c×n所以f(n)=O(n)由此看出，DC3算法是一个优秀的线性算法！后缀数组的应用例1：如果字符串L同时出现在字符串A和字符串B中，则称字符串L是字符串A和字符串B的公共子串。给定两个字符串A和B，求最长公共子串。例如：字符串“aaaba”和“abaa”的最长公共子串为“aba”height数组定义height[i]=suffix(sa[i-1])和suffix(sa[i])的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀。那么对于j和k，不妨设rank[j]

5、：height数组suffix(j)和suffix(k)的最长公共前缀为height[rank[j]+1],height[rank[j]+2],height[rank[j]+3],…,height[rank[k]]中的最小值。例如，字符串为“aabaaaab”，求后缀“abaaaab”和后缀“aaab”的最长公共前缀。例1最长公共子串字符串的任何一个子串都是这个字符串的某个后缀的前缀。求A和B的最长公共子串等价于求A的后缀和B的后缀的最长公共前缀的最大值。将第二个字符串写在第一个字符串后面，中间用一个没有出现过的字符隔开，再求这个新的字符串的后缀数组。如何高效的计算hei

6、ght数组？如果按height[2]，height[3]，……，height[n]的顺序计算，最坏情况下时间复杂度为O(n2)。这样做并没有利用字符串的性质。定义h[i]=height[rank[i]]，也就是suffix(i)和在它前一名的后缀的最长公共前缀。h数组有以下性质：h[i]≥h[i-1]-1最长公共前缀为h[i-1]最长公共前缀至少为h[i-1]-1如何高效的计算height数组？按照h[1],h[2],……,h[n]的顺序计算,并利用h数组的性质，时间复杂度可以降为O(n)。例1最长公共子串（1）连接两个字符串（2）求后缀数组（3）求height数组（4）

7、求排名相邻但原来不在同一个字符串中的两个后缀的height值的最大值。时间复杂度已经取到下限，由此看出，这是一个非常优秀的算法。O(

8、A

9、+

10、B

11、)总结后缀数组是字符串处理中非常优秀的数据结构，是一种处理字符串问题的有力工具。我们应该掌握好后缀数组这种数据结构，并且能在不同类型的题目中灵活、高效的运用。更多内容……第一部分后缀数组的实现(1)倍增算法时间复杂度O(nlogn)(2)DC3算法时间复杂度O(n)第二部分后缀数组的应用(1)最长公共前缀(2)单个字符串的相关问题(3)两个字符串的相关问题(4)多个字符串的相关问题完