算法合集之《后缀数组-处理字符串的有力工具》.ppt

《算法合集之《后缀数组-处理字符串的有力工具》.ppt》由会员分享，可在线阅读，更多相关《算法合集之《后缀数组-处理字符串的有力工具》.ppt（31页珍藏版）》请在三一办公上搜索。

1、处理字符串的有力工具-,华南师范大学附属中学 罗穗骞指导教师：张学东,后缀数组,目录,第一部分 后缀数组的实现 DC3算法第二部分 后缀数组的应用 例1:求两个字符串的最长公共子串,基本定义,【后缀数组SA】后缀数组保存的是一个字符串的所有后缀的排序结果。其中SAi保存的是字符串所有的后缀中第i小的后缀的开头位置。【名次数组Rank】名次数组Ranki保存的是后缀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)

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

5、uffix(k)的最长公共前缀为heightrankj+1,heightrankj+2,heightrankj+3,heightrankk中的最小值。例如，字符串为“aabaaaab”，求后缀“abaaaab”和后缀“aaab”的最长公共前缀。,例1 最长公共子串,字符串的任何一个子串都是这个字符串的某个后缀的前缀。求A和B的最长公共子串等价于求A的后缀和B的后缀的最长公共前缀的最大值。将第二个字符串写在第一个字符串后面，中间用一个没有出现过的字符隔开，再求这个新的字符串的后缀数组。,如何高效的计算height数组？,如果按height2，height3，heightn的顺序计算，最坏情况下时

6、间复杂度为O(n2)。这样做并没有利用字符串的性质。定义hi=heightranki，也就是suffix(i)和在它前一名的后缀的最长公共前缀。h数组有以下性质：,hihi-1-1,最长公共前缀为hi-1,最长公共前缀至少为hi-1-1,如何高效的计算height数组？,按照h1,h2,hn的顺序计算,并利用h数组的性质，时间复杂度可以降为O(n)。,例1 最长公共子串,（1）连接两个字符串（2）求后缀数组（3）求height数组（4）求排名相邻但原来不在同一个字符串中的两个后缀的height值的最大值。时间复杂度已经取到下限，由此看出，这是一个非常优秀的算法。,O(|A|+|B|),总结,后缀数组是字符串处理中非常优秀的数据结构，是一种处理字符串问题的有力工具。我们应该掌握好后缀数组这种数据结构，并且能在不同类型的题目中灵活、高效的运用。,更多内容,第一部分 后缀数组的实现(1)倍增算法 时间复杂度O(nlogn)(2)DC3算法 时间复杂度O(n)第二部分 后缀数组的应用(1)最长公共前缀(2)单个字符串的相关问题(3)两个字符串的相关问题(4)多个字符串的相关问题,完整的代码,共13个例题,原题,解答,参考程序,25行,40行,谢谢观看！,欢迎提问！,