算法合集之《后缀数组》.ppt

《算法合集之《后缀数组》.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、后缀数组芜湖一中　许智磊后缀数组——字符串处理中的有力武器后缀树的一个简单而高效的替代品当今字符串处理研究中的热门让我们一同揭开她神秘的面纱后缀数组——定义和符号字符集、字符、字符串都按照惯常的定义字符串S的长度表示为len(S)字符串的下标从1开始到len(S)结束字符串S的第i个字符表示为S[i]从i到j这一段的子串表示为S[i..j]后缀是一种特殊的子串从某个位置i开始到整个串的末尾结束S的从i开头的后缀等价于S[i..len(S)]后缀数组——定义和符号约定一个字符集Σ待处理的字符串约定为S，约定len(S)=n规定S以字符“$”结尾，

2、即S[n]=“$”“$”小于Σ中所有的字符除了S[n]=“$”之外，S的其他字符都属于Σ对于约定的字符串S，其i开头的后缀表示为Suffix(i)后缀数组——定义和符号字符串的大小关系按照通常所说的“字典顺序”进行比较我们对S的n个后缀按照字典顺序从小到大排序将排序后的后缀的开头位置顺次放入数组SA中，称为后缀数组令Rank[i]保存Suffix(i)在排序中的名次，称数组Rank为名次数组后缀数组——构造方法把n个后缀当作n个字符串，按照普通的方法进行排序——O(n2)低效的原因——把后缀仅仅当作普通的、独立的字符串，忽略了后缀之间存在的有机

3、联系。如何构造后缀数组?后缀数组——构造方法倍增算法(DoublingAlgorithm)对字符串u，定义uk=u[1..k],len(u)≥ku,len(u)

4、符相当于在k-前缀意义下比较Suffix(i)和Suffix(j)比较绿色字符相当于在k-前缀意义下比较Suffix(i+k)和Suffix(j+k)在2k-前缀意义下比较两个后缀可以转化成在k-前缀意义下比较两个后缀i+kj+k后缀数组——构造方法把n个后缀按照k-前缀意义下的大小关系从小到大排序将排序后的后缀的开头位置顺次放入数组SAk中，称为k-后缀数组用Rankk[i]保存Suffix(i)在排序中的名次，称数组Rankk为k-名次数组后缀数组——构造方法利用SAk可以在O(n)时间内求出Rankk利用Rankk可以在常数时间内对两个后

5、缀进行k-前缀意义下的大小比较后缀数组——构造方法如果已经求出Rankk可以在常数时间内对两个后缀进行k-前缀意义下的比较可以在常数时间内对两个后缀进行2k-前缀意义下的比较可以很方便地对所有的后缀在2k-前缀意义下排序采用快速排序O(nlogn)采用基数排序O(n)可以在O(n)时间内由Rankk求出SA2k也就可以在O(n)时间内求出Rank2k后缀数组——构造方法1-前缀比较关系实际上是对字符串的第一个字符进行比较可以直接根据开头字符对所有后缀进行排序求出SA1采用快速排序，复杂度为O(nlogn)然后根据SA1在O(n)时间内求出Ran

6、k1可以在O(nlogn)时间内求出SA1和Rank1后缀数组——构造方法直接根据首字符排序SA1Rank1O(nlogn)SA2Rank2O(n)SA4Rank4O(n)SA8Rank8O(n)……O(n)SAmRankmO(n)m=2t且m≥nO(nlogn)的操作一次O(n)的操作[logn]次总复杂度为O(nlogn)后缀数组——构造方法当m≥n时，对任意u=Suffix(x)，um=uSuffix(i)≤mSuffix(j)Suffix(i)≤Suffix(j)Suffix(i)

7、nlogn)求出SAm和Rankm可以在O(nlogn)时间内求出后缀数组SA和名次数组Rank后缀数组——构造方法m≥n，SAm=SARankm=Rank我们已经在O(nlogn)的时间内构造出了后缀数组SA和名次数组Rank后缀数组——方法总结利用到后缀之间的联系用k-前缀比较关系来表达2k-前缀比较关系每次可以将参与比较的前缀长度加倍根据SAk、Rankk求出SA2k、Rank2k参与比较的前缀长度达到n以上时结束倍增思想后缀数组——辅助工具仅仅靠后缀数组和名次数组有时候还不能很好地处理问题后缀数组的最佳搭档——LCP定义两个字符串的最长

8、公共前缀LongestCommonPrefixlcp(u,v)=max{i

9、u=iv}也就是从头开始比较u和v的对应字符持续相等的最远值后缀数组——辅