算法合集之后缀数组.pptx

后缀数组 芜湖一中许智磊后缀数组字符串处理中的有力武器后缀树的一个简单而高效的替代品当今字符串处理研究中的热门让我们一同揭开她神秘的面纱后缀数组定义和符号字符集、字符、字符串都按照惯常的定义字符串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)对字符串u，定义uk=u1.k,len(u)ku,len(u)k定义k-前缀比较关系k，=k和k对两个字符串u,v，ukv当且仅当ukvku=kv当且仅当uk=vkukv当且仅当ukvk后缀数组构造方法设u=Suffix(i)，v=Suffix(j)后缀u，以i开头后缀v，以i开头对u、v在2k-前缀意义下进行比较kkkk比较红色字符相当于在k-前缀意义下比较Suffix(i)和 Suffix(j)比较绿色字符相当于在k-前缀意义下比较Suffix(i+k)和 Suffix(j+k)在2k-前缀意义下比较两个后缀可以转化成在k-前缀意义下比较两个后缀i+kj+k后缀数组构造方法把n个后缀按照k-前缀意义下的大小关系从小到大排序将排序后的后缀的开头位置顺次放入数组SAk中，称为k-后缀数组用Rankki保存Suffix(i)在排序中的名次，称数组Rankk为k-名次数组后缀数组构造方法利用SAk可以在O(n)时间内求出Rankk利用Rankk可以在常数时间内对两个后缀进行k-前缀意义下的大小比较后缀数组构造方法如果已经求出Rankk可以在常数时间内对两个后缀进行k-前缀意义下的比较可以在常数时间内对两个后缀进行2k-前缀意义下的比较可以很方便地对所有的后缀在2k-前缀意义下排序采用快速排序O(nlogn)采用基数排序O(n)可以在O(n)时间内由Rankk求出SA2k也就可以在O(n)时间内求出Rank2k 后缀数组构造方法1-前缀比较关系实际上是对字符串的第一个字符进行比较可以直接根据开头字符对所有后缀进行排序求出SA1采用快速排序，复杂度为O(nlogn)然后根据SA1在O(n)时间内求出Rank1可以在可以在O(nlogn)时间内求出时间内求出SA1和和Rank1后缀数组构造方法直接根据首字符排序SA1Rank1O(nlogn)SA2Rank2O(n)SA4Rank4O(n)SA8Rank8O(n)O(n)SAmRankmO(n)m=2t且mnO(nlogn)的操作一次O(n)的操作logn次总复杂度为O(nlogn)后缀数组构造方法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值的最小值最小值后缀数组辅助工具 4=LCP(i,i+1)3=LCP(i+1,i+2)5=LCP(i+2,j)LCP(i,j)=3Suffix(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)可以在常数时间常数时间内计算出任何两个后缀的最长公共前缀最长公共前缀这是后缀数组最常用以及最强大的功能之一后缀数组应用举例怎样使用后缀数组？后缀数组应用举例回文串回文串顺读和倒读完全一样的字符串奇回文串奇回文串字符串u满足：1.len(u)=p为奇数2.对任何1i(p-1)/2，ui=up-i+1偶回文串偶回文串字符串v满足：1.len(v)=q为奇数2.对任何1iq/2，vi=vq-i+1回文串回文串后缀数组应用举例字符串T的回文子串回文子串T的子串子串，并且是回文串回文串字符串T的最长回文子串最长回文子串T的回文子串回文子串中长度最大最大的给出一个字符串T，求它的最长回文子串给出最大长度即可设len(T)=m后缀数组应用举例分析求最长奇回文子串的算法最长偶回文子串可以类似求出后缀数组应用举例枚举奇回文串中间一个字符的位置尽量向两边扩展后缀数组应用举例 r r ii-r-1 i+r+1反射相等以某个位置为中心向两边扩展的复杂度为O(m)整个算法的复杂度为O(m2)后缀数组应用举例求以一个位置i为中心向两边扩展的最远值是算法的核心部分需要降低这一步的复杂度后缀数组应用举例$中心 ii=2m-i+2i-ri+ri+r#求以i为中心向两边扩展的最远值，等价于求Suffix(i)和Suffix(i)的最长公共前缀后缀数组！后缀数组！同时和粉红串反射相等T串T串Suffix(i)和Suffix(i)的公共前缀后缀数组应用举例解法：1.初始化答案为0。按照前述方法修改串T，得到串S2.求出后缀数组SA、名次数组Rank3.计算height数组并进行标准RMQ方法预处理复杂度：设len(S)=n，则n=2m+2O(m)+O(nlogn)+m*O(1)=O(nlogn)4.枚举i，计算以i为中心向两边扩展的最远值并更新答案+2*O(n)后缀数组 VS 后缀树后缀树也可以做到类似的事情后缀数组有什么优势呢？后缀数组 VS 后缀树后缀数组在信息学竞赛中最大的优势：易于理解易于理解，易于编程易于编程，易于调试易于调试后缀数组比后缀树占用的空间少后缀数组比后缀树占用的空间少处理长字符串，如DNA分析后缀数组 VS 后缀树时间复杂度的比较按照字符总数|把字符集分为三种类型：Constant Alphabet|是一个常数Integer Alphabet|为字符串长度n的多项式函数General Alphabet 对|没有任何限制Constant AlphabetInteger AlphabetGeneral Alphabet后缀数组 VS 后缀树后缀数组是直接针对General Alphabet设计的算法复杂度跟字符集的类型没有关系后缀树则对不同字符集有不同的表现如果采用儿子-兄弟方式来表达后缀树：构造的复杂度为O(n*|)显然不适合Integer和General Alphabet，对于|稍大的Constant Alphabet也无法胜任解决方法：每个节点建立一棵红红黑黑树树来保存儿子，复杂度为O(n*log|)。竞赛的时候有时间编吗？结论对于Integer和General以及|较大的Constant Alphabet，后缀树甚至在时间复杂度上都无法胜过后缀数组。但是对于|较小的Constant Alphabet，后缀树还是有着速度上的优势的。我们要根据实际情况，因“题”制宜选择合适的数据结构后缀数组最后的话研究后缀数组，不是因为害怕后缀树的繁琐也没有贬低后缀树，抬高后缀数组的意思对于功能相似的两个数据结构，我们应该灵活地掌握，有比较有选择地使用构造后缀数组用到的倍增思想对我们的思考也是有帮助的后缀数组