《算法合集之《后缀数组--处理字符串的有力工具》.ppt》由会员分享，可在线阅读，更多相关《算法合集之《后缀数组--处理字符串的有力工具》.ppt（31页珍藏版）》请在金锄头文库上搜索。
1、处理字符串的有力工具-华南师范大学附属中学 罗穗骞指导教师：张学东后缀数组目录n第一部分 后缀数组的实现n DC3算法n第二部分 后缀数组的应用n 例1: 求两个字符串的最长公共子串基本定义n【后缀数组SA】后缀数组保存的是一个字符串的所有后缀的排序结果。其中SAi保存的是字符串所有的后缀中第i小的后缀的开头位置。n【名次数组Rank】名次数组Ranki保存的是后缀i在所有后缀中从小到大排列的“名次”。n为了叙述方便，以第k个字符开始的后缀称为后缀k。基本定义n以字符串“aabaaaab”为例。DC3算法n复杂 难以实现仅40行代码DC3算法n（1）、先将后缀分成两部分，然后对第一部分的后缀排
2、序。n（2）、利用（1）的结果，对第二部分的后缀排序。n（3）、将（1）和（2）的结果合并，即完成对所有后缀排序。（1）、将后缀分成两部分n字符的编号从0开始。n将后缀分成两部分：n第一部分是后缀k（k模3不等于0）n第二部分是后缀k（k模3等于0）对第一部分的后缀排序。n为了方便接下来的操作，这里要求字符串必须以一个最小的字符结尾。suffix(1)suffix(2)递归后缀数组步骤（1）完成DC3算法n（1）、先将后缀分成两部分，然后对第一部分的后缀排序。n（2）、利用（1）的结果，对第二部分的后缀排序。n（3）、将（1）和（2）的结果合并，即完成对所有后缀排序。（2）、对第二部分的后缀排
3、序第一关键字第二关键字基数排序即可步骤（2）完成DC3算法n（1）、先将后缀分成两部分，然后对第一部分的后缀排序。n（2）、利用（1）的结果，对第二部分的后缀排序。n（3）、将（1）和（2）的结果合并，即完成对所有后缀排序。（3）、将(1)和(2)的结果合并每次的比较都可以高效的完成 步骤（3）完成算法分析 n假设这个算法的时间复杂度为f(n)。n第（1）步排序的时间为O(n)（一般来说，m比较小，这里忽略不计）,新的字符串的长度不超过2n/3，求新字符串的sa的时间为f(2n/3)。n第（2）和第（3）步的时间都是O(n)。 算法分析f(n) = O(n) + f(2n/3)f(n) cn
4、+ f(2n/3)f(n)cn+c(2n/3)+c(4n/9)+3cn所以 f(n)=O(n)n由此看出，DC3算法是一个优秀的线性算法！后缀数组的应用n例1：如果字符串L同时出现在字符串A和字符串B中，则称字符串L是字符串A和字符串B的公共子串。 n给定两个字符串A和B，求最长公共子串。n例如：字符串“aaaaabaaba”和“abaabaa a”的最长公共子串为“abaaba”height数组n定义nheighti=suffix(sai-1)和suffix(sai)的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀。n那么对于j和k，不妨设rankjrankk,则有以下性质：heigh
5、t数组nsuffix(j)和suffix(k)的最长公共前缀为heightrankj+1, heightrankj+2, heightrankj+3, ,heightrankk中的最小值。n例如，字符串为“aabaaaab”，求后缀“abaaaab”和后缀“aaab”的最长公共前缀。例1 最长公共子串n 字符串的任何一个子串都是这个字符串的某个后缀的前缀。求A和B的最长公共子串等价于求A的后缀和B的后缀的最长公共前缀的最大值。n 将第二个字符串写在第一个字符串后面，中间用一个没有出现过的字符隔开，再求这个新的字符串的后缀数组。如何高效的计算height数组？n如果按height2，height
6、3，heightn的顺序计算，最坏情况下时间复杂度为O(n2)。这样做并没有利用字符串的性质。定义hi=heightranki，也就是suffix(i)和在它前一名的后缀的最长公共前缀。h数组有以下性质：hihi-1-1最长公共前缀为hi-1最长公共前缀至少为hi-1-1如何高效的计算height数组？n按照h1,h2,hn的顺序计算,并利用h数组的性质，时间复杂度可以降为O(n)。例1 最长公共子串n（1）连接两个字符串n（2）求后缀数组n（3）求height数组n（4）求排名相邻但原来不在同一个字符串中的两个后缀的height值的最大值。n时间复杂度已经取到下限，由此看出，这是一个非常优秀的算法。O(|A|+|B|)总结n 后缀数组是字符串处理中非常优秀的数据结构，是一种处理字符串问题的有力工具。n 我们应该掌握好后缀数组这种数据结构，并且能在不同类型的题目中灵活、高效的运用。更多内容n第一部分 后缀数组的实现n (1) 倍增算法 时间复杂度O(nlogn)n (2) DC3算法 时间复杂度O(n)n第二部分 后缀数组的应用n (1) 最长公共前缀n (2) 单个字符串的相关问题n (3) 两个字符串的相关问题n (4) 多个字符串的相关问题完整的代码共13个例题原题解答参考程序25行40行
