算法合集之《后缀数组》.ppt
后缀数组,芜湖一中许智磊,后缀数组字符串处理中的有力武器,后缀树的一个简单而高效的替代品,当今字符串处理研究中的热门,让我们一同揭开她神秘的面纱,后缀数组定义和符号,字符集、字符、字符串都按照惯常的定义,字符串S的长度表示为len(S)字符串的下标从1开始到len(S)结束,字符串S的第i个字符表示为Si从i到j这一段的子串表示为Si.j,后缀是一种特殊的子串从某个位置i开始到整个串的末尾结束S的从i开头的后缀等价于Si.len(S),后缀数组定义和符号,约定一个字符集待处理的字符串约定为S，约定len(S)=n,规定S以字符“$”结尾，即Sn=“$”“$”小于中所有的字符除了Sn=“$”之外，S的其他字符都属于,对于约定的字符串S，其i开头的后缀表示为Suffix(i),后缀数组定义和符号,字符串的大小关系按照通常所说的“字典顺序”进行比较,我们对S的n个后缀按照字典顺序从小到大排序将排序后的后缀的开头位置顺次放入数组SA中，称为后缀数组,令Ranki保存Suffix(i)在排序中的名次，称数组Rank为名次数组,后缀数组构造方法,把n个后缀当作n个字符串，按照普通的方法进行排序 O(n2),低效的原因 把后缀仅仅当作普通的、独立的字符串，忽略了后缀之间存在的有机联系。,如何构造后缀数组?,后缀数组构造方法,倍增算法(Doubling Algorithm),定义k-前缀比较关系k，=k和k对两个字符串u,v，ukv当且仅当ukvku=kv当且仅当uk=vkukv当且仅当ukvk,后缀数组构造方法,u,v,ukv?u=kv?ukv?,u,v,u2kv?u=2kv?u2kv?,后缀数组构造方法,设u=Suffix(i)，v=Suffix(j),后缀u，以i开头,后缀v，以i开头,对u、v在2k-前缀意义下进行比较,比较红色字符相当于在k-前缀意义下比较Suffix(i)和 Suffix(j),比较绿色字符相当于在k-前缀意义下比较Suffix(i+k)和 Suffix(j+k),在2k-前缀意义下比较两个后缀可以转化成在k-前缀意义下比较两个后缀,后缀数组构造方法,把n个后缀按照k-前缀意义下的大小关系从小到大排序将排序后的后缀的开头位置顺次放入数组SAk中，称为k-后缀数组,用Rankki保存Suffix(i)在排序中的名次，称数组Rankk为k-名次数组,后缀数组构造方法,利用SAk可以在O(n)时间内求出Rankk,利用Rankk可以在常数时间内对两个后缀进行k-前缀意义下的大小比较,后缀数组构造方法,如果已经求出Rankk,采用快速排序O(nlogn)采用基数排序O(n),后缀数组构造方法,1-前缀比较关系实际上是对字符串的第一个字符进行比较,后缀数组构造方法,直接根据首字符排序,m=2t且mn,后缀数组构造方法,O(nlogn)求出SAm和Rankm,可以在O(nlogn)时间内求出后缀数组SA和名次数组Rank,后缀数组构造方法,mn，SAm=SARankm=Rank,我们已经在O(nlogn)的时间内构造出了后缀数组SA 和 名次数组Rank,后缀数组方法总结,利用到后缀之间的联系用k-前缀比较关系来表达2k-前缀比较关系,每次可以将参与比较的前缀长度加倍根据SAk、Rankk求出SA2k、Rank2k,参与比较的前缀长度达到n以上时结束,倍增思想,后缀数组辅助工具,仅仅靠后缀数组和名次数组有时候还不能很好地处理问题,后缀数组的最佳搭档LCP,定义两个字符串的最长公共前缀Longest Common Prefixlcp(u,v)=maxi|u=iv也就是从头开始比较u和v的对应字符持续相等的最远值,后缀数组辅助工具,定义LCP(i,j)=lcp(Suffix(SAi),Suffix(SAj),也就是SA数组中第i个和第j个后缀的最长公共前缀,LCP Theorem对任何1ijnLCP(i,j)=minLCP(k-1,k)|i+1kj,称j-i为LCP(i,j)的“跨度”，LCP Theorem意义为：跨度大于1的LCP值可以表示成一段跨度等于1的LCP值的最小值,若ijLCP(i,j)=LCP(j,i),可以用跨度为1的LCP值来表示任何一个LCP值,后缀数组辅助工具,定义LCP(i,j)=lcp(Suffix(SAi),Suffix(SAj),也就是SA数组中第i个和第j个后缀的最长公共前缀,LCP Theorem对任何1ijnLCP(i,j)=minLCP(k-1,k)|i+1kj,称j-i为LCP(i,j)的“跨度”，LCP Theorem意义为：跨度大于1的LCP值可以表示成一段跨度等于1的LCP值的最小值,后缀数组辅助工具,Suffix(SAi),Suffix(SAj),Suffix(SAi+1),Suffix(SAi+2),后缀数组辅助工具,设heighti=LCP(i-1,i),根据LCP TheoremLCP(i,j)=minheightk|i+1kj,计算LCP(i,j)等价于询问数组height中下标从 i+1 到 j 范围内所有元素的最小值,经典的RMQ(Range Minimum Query)问题!,线段树、排序树 O(nlogn)预处理,O(logn)每次询问标准RMQ方法 O(n)预处理,O(1)每次询问,后缀数组辅助工具,采用一种“神奇的”方法，可以在O(n)时间内计算出height数组,采用标准RMQ方法在O(n)时间内进行预处理,之后就可以在常数时间内算出任何的LCP(i,j),根据lcp(Suffix(i),Suffix(j)=LCP(Ranki,Rankj),可以在常数时间内计算出任何两个后缀的最长公共前缀,后缀数组辅助工具,采用一种“神奇的”方法，可以在O(n)时间内计算出height数组,采用标准RMQ方法在O(n)时间内进行预处理,之后就可以在常数时间内算出任何的LCP(i,j),可以在常数时间内计算出任何两个后缀的最长公共前缀,这是后缀数组最常用以及最强大的功能之一,后缀数组应用举例,几个常见的问题,问题一给定一个字符串S，对它的所有后缀进行排序。,问题二给定一个待匹配串S，每次输入一个模式串P，要求返回P在S中的一个匹配的开头位置，或者返回无匹配。,问题三给定一个字符串S，求出S中的最长回文子串。,O(n2),O(m+n),O(n2),O(nlogn),O(m+logn),O(nlogn),后缀数组应用举例,怎样使用后缀数组？,后缀数组应用举例,回文串顺读和倒读完全一样的字符串,奇回文串字符串u满足：len(u)=p为奇数对任何1i(p-1)/2，ui=up-i+1,偶回文串字符串v满足：len(v)=q为奇数对任何1iq/2，vi=vq-i+1,后缀数组应用举例,字符串T的回文子串T的子串，并且是回文串,字符串T的最长回文子串T的回文子串中长度最大的,给出一个字符串T，求它的最长回文子串,给出最大长度即可设len(T)=m,后缀数组应用举例,分析求最长奇回文子串的算法最长偶回文子串可以类似求出,后缀数组应用举例,枚举奇回文串中间一个字符的位置尽量向两边扩展,后缀数组应用举例,以某个位置为中心向两边扩展的复杂度为O(m)整个算法的复杂度为O(m2),后缀数组应用举例,求以一个位置i为中心向两边扩展的最远值是算法的核心部分需要降低这一步的复杂度,后缀数组应用举例,$,#,求以i为中心向两边扩展的最远值，等价于求Suffix(i)和Suffix(i)的最长公共前缀,后缀数组！,同时和粉红串反射相等,T串,T串,Suffix(i)和Suffix(i)的公共前缀,后缀数组应用举例,解法：,初始化答案为0。按照前述方法修改串T，得到串S,求出后缀数组SA、名次数组Rank,计算height数组并进行标准RMQ方法预处理,复杂度：设len(S)=n，则n=2m+2,O(m),+O(nlogn),+m*O(1),=O(nlogn),枚举i，计算以i为中心向两边扩展的最远值并更新答案,+2*O(n),后缀数组 VS 后缀树,后缀树也可以做到类似的事情,后缀数组有什么优势呢？,后缀数组 VS 后缀树,后缀数组在信息学竞赛中最大的优势：易于理解，易于编程，易于调试,后缀数组比后缀树占用的空间少处理长字符串，如DNA分析,后缀数组 VS 后缀树,时间复杂度的比较,按照字符总数|把字符集分为三种类型：,Constant Alphabet|是一个常数,Integer Alphabet|为字符串长度n的多项式函数,General Alphabet 对|没有任何限制,后缀数组 VS 后缀树,后缀数组是直接针对General Alphabet设计的算法复杂度跟字符集的类型没有关系,后缀树则对不同字符集有不同的表现,如果采用儿子-兄弟方式来表达后缀树：构造的复杂度为O(n*|)显然不适合Integer和General Alphabet，对于|稍大的Constant Alphabet也无法胜任,解决方法：每个节点建立一棵红黑树来保存儿子，复杂度为O(n*log|)。竞赛的时候有时间编吗？,结论对于Integer和General以及|较大的Constant Alphabet，后缀树甚至在时间复杂度上都无法胜过后缀数组。但是对于|较小的Constant Alphabet，后缀树还是有着速度上的优势的。我们要根据实际情况，因“题”制宜选择合适的数据结构,后缀数组最后的话,研究后缀数组，不是因为害怕后缀树的繁琐,也没有贬低后缀树，抬高后缀数组的意思,对于功能相似的两个数据结构，我们应该灵活地掌握，有比较有选择地使用,构造后缀数组用到的倍增思想对我们的思考也是有帮助的,后缀数组,谢谢大家！,后缀数组关于“$”,为什么规定S以“$”结尾？,后缀数组关于“$”,设u=Suffix(i)，v=Suffix(j),后缀u，以i开头,后缀v，以i开头,对u、v在2k-前缀意义下进行比较,比较红色字符相当于在k-前缀意义下比较Suffix(i)和 Suffix(j),比较绿色字符相当于在k-前缀意义下比较Suffix(i+k)和 Suffix(j+k),在2k-前缀意义下比较两个后缀可以转化成在k-前缀意义下比较两个后缀,后缀数组关于“$”,i,j,i+k,j+k?大于n!,$,“$”小于对应的字符,不相等,后缀数组关于“$”,结尾的“$”避免了下标越界造成无意义表达式的麻烦,为什么规定“$”小于中的任何字符？规定“$”不等于中的任何字符可以达到同样的目的？,后缀数组关于“$”,i,j,$,相等,i开头的后缀 j开头的后缀,$小于对应字符,仍然能得到i开头的后缀 j开头的后缀,原串,新串,后缀数组关于“$”,规定“$”小于中的任何字符是为了保证在串S结尾添加“$”改造为S之后，S中的后缀之间的大小关系在S中依然成立。于是S的后缀数组、名次数组都和S的一样。,另外不难看出S的height数组和S的也是一样的。,在待处理的串后添加“$”不会影响结果的正确性，只是令操作变得方便。,后缀数组关于“$”,后缀数组关于“#”,为什么要先在T串后加“#”然后再反射T串？,后缀数组关于“#”,$,i,#,T串,T串,Suffix(i)和Suffix(i)的公共前缀,Suffix(i)和Suffix(i)的最长公共前缀不再能准确地反映向两边扩展的最远值因为左边的浅绿色串用到了T中的字符这是不合实际的,后缀数组关于“#”,在T的结尾加上“#”保证了Suffix(i)和Suffix(i)的最长公共前缀能正确反映以i为中心向两边扩展的最远值,特殊判断也可以做到这一点，但是加一个“#”稍微方便一些。,后缀数组关于线性算法,采用Farach的构造方法，对于Integer Alphbet，可以在O(n)时间内构造出后缀树,我们不打算把Farach方法列入考察范围,这个算法实现极为繁琐更像是挖空心思将几个算法凑在一起的“大杂烩”竞赛的有限时间内几乎无法完成,后缀数组关于线性算法,后缀数组关于线性算法,即使构造完成了，如果想使用后缀树，还是得想办法处理每个节点指向儿子的指针。,对字符总数太大的情况只能排序存储时间复杂度立刻增加到O(nlog|)并没有得到改善，也未必比后缀数组快,后缀数组关于线性算法,访问的时候要二分查找指向儿子的指针几乎所有的基本操作复杂度都要乘上系数 log|某些情况下甚至比后缀数组差，如多模式串匹配,后缀数组关于线性算法,只有极少数情况下后缀树才能真正做到线性时间构造，常数时间基本操作,Farach构造方法的理论价值大于它在竞赛中的实际价值,不适合拿来和本文所讲的后缀数组相比,后缀数组关于线性算法,更令人吃惊的是后缀数组也有对Integer Alphbet情况下线性构造的算法,这是一种三分法，比Farach方法优美得多,但是我们也无意在本文中探讨,后缀数组关于线性算法,虽然说它比Farach方法优美，但是实现起来仍然比倍增算法繁得多不适合在竞赛中使用有兴趣的同学可以自行研究,三分法的技巧性显得较强与技巧相比我更加欣赏倍增算法所体现出的深刻思想,后缀数组关于空间,从Rankk推出SAk和Rank2k需要两个数组（共2n个整数）以实现基数排序同一时刻Rankk和Rank2k只需要保存一个SA2k可以直接覆盖SAk2n个整数保存结果+2n个整数辅助计算技巧性地操作可以将辅助计算的空间减少至n个整数,后缀数组关于空间,后缀树通常有2n个以上节点通常每个节点要两个整数，至少要保存一个整数每个节点两个指针4n个指针+2n个整数至少是 4n个指针+n个整数,后缀数组关于空间,为什么不算上height数组和RMQ预处理的空间？为了处理问题，后缀树需要预处理以便计算节点的最近公共祖先（Least Common Ancestor）LCA问题和RMQ问题是等价的后缀树预处理的空间占用和后缀数组基本一样,后缀数组关于RMQ,RMQ问题的标准解法是怎么做的？同样用到了倍增思想对每个位置i记录从开始向后1,2,4,8.长度的一段中的最小值总共有nlogn个值，通过动态规划计算,后缀数组关于RMQ,采用对待询问数组建立Treap的方法转化为0-1 RMQ采用模板方法将复杂度降为线性竞赛中用O(nlogn)预处理的方法已经足够,后缀数组关于倍增思想,倍增思想，本质上是一种特殊的动态规划思想与一般的动态规划不同的是，它划分阶段是按照规模的对数来分也就是先处理规模为20的问题然后顺次推出规模为21，22，23，.的问题,后缀数组关于倍增思想,关键在于找到2k到2k+1转换的桥梁本文中的桥梁就是2k-前缀比较关系可以转化为k-前缀比较关系,后缀数组关于倍增思想,知易行难要用好用活倍增思想不是那么简单的事情难点也就在于寻找转化的桥梁,后缀数组关于倍增思想,道德经云：道生一，一生二，二生三，三生万物是否能用好倍增思想，做到：一生二，二生四，四生八，要看各人的道行如何了,后缀数组关于倍增思想,如果能够用好倍增思想虽然不见得能化生万物但是相信能够在很多情况下帮助你独辟蹊径，解决规模巨大的题目举重若轻挥洒自如,
