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

处理字符串的有力工具---华南师范大学附属中学罗穗骞指导教师：张学东后缀数组目录第一部分后缀数组的实现DC3算法第二部分后缀数组的应用例1:求两个字符串的最长公共子串基本定义【后缀数组SA】后缀数组保存的是一个字符串的所有后缀的排序结果。其中SA[i]保存的是字符串所有的后缀中第i小的后缀的开头位置。【名次数组Rank】名次数组Rank[i]保存的是后缀i在所有后缀中从小到大排列的“名次”。为了叙述方便，以第k个字符开始的后缀称为后缀k。基本定义以字符串“aabaaaab”为例。DC3算法复杂难以实现仅40行代码DC3算法（1）、先将后缀分成两部分，然后对第一部分的后缀排序。（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）、对第二部分的后缀排序第一关键字第二关键字基数排序即可步骤（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+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]rank[k],则有以下性质：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的后缀的最长公共前缀的最大值。将第二个字符串写在第一个字符串后面，中间用一个没有出现过的字符隔开，再求这个新的字符串的后缀数组。如何高效的计算height数组？如果按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）求排名相邻但原来不在同一个字符串中的两个后缀的height值的最大值。时间复杂度已经取到下限，由此看出，这是一个非常优秀的算法。O(|A|+|B|)总结后缀数组是字符串处理中非常优秀的数据结构，是一种处理字符串问题的有力工具。我们应该掌握好后缀数组这种数据结构，并且能在不同类型的题目中灵活、高效的运用。更多内容……第一部分后缀数组的实现(1)倍增算法时间复杂度O(nlogn)(2)DC3算法时间复杂度O(n)第二部分后缀数组的应用(1)最长公共前缀(2)单个字符串的相关问题(3)两个字符串的相关问题(4)多个字符串的相关问题25行40行