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

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

1、IOI2004国家集训队论文许智磊后缀数组安徽省芜湖市第一中学许智磊【摘要】本文介绍后缀数组的基本概念、方法以及应用。首先介绍O(nlogn)复杂度构造后缀数组的倍增算法，接着介绍了配合后缀数组的最长公共前缀LCP（LongestCommonPrefix）的计算方法，并给出一个线性时间内计算height数组（记录跨度为1的LCP值的数组）的算法。为了让读者对如何运用后缀数组有一个感性认识，还介绍了两个应用后缀数组的例子：多模式串的模式匹配（给出每次匹配O(m+logn)时间复杂度的算法）以及求最长回文子串（给出O(nlogn)时间复杂度的算法）。最后对后缀数组和后缀树作了一番比

2、较。【关键字】字符串后缀k-前缀比较关系后缀数组名次数组后缀树倍增算法基数排序最长公共前缀RMQ问题模式匹配回文串最长回文子串【正文】在字符串处理当中，后缀树和后缀数组都是非常有力的工具，其中后缀树大家了解得比较多，关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。可以说，在信息学竞赛中后缀数组比后缀树要更为实用。因此在本文中笔者想介绍一下后缀数组的基本概念、构造方法，以及配合后缀数组的最长公共前缀数组的构造方法，最后结合一些例子谈谈后缀数组的

3、应用。第1页共11页IOI2004国家集训队论文许智磊基本概念首先明确一些必要的定义：字符集一个字符集Σ是一个建立了全序关系的集合，也就是说，Σ中的任意两个不同的元素α和β都可以比较大小，要么α<β，要么β<α（也就是α>β）。字符集Σ中的元素称为字符。字符串一个字符串S是将n个字符顺次排列形成的数组，n称为S的长度，表示为len(S)。S的第i个字符表示为S[i]。子串字符串S的子串S[i..j]，i≤j，表示S串中从i到j这一段，也就是顺次排列S[i],S[i+1],...,S[j]形成的字符串。后缀后缀是指从某个位置i开始到整个串末尾结束的一个特殊子串。字符串S的从i开头

4、的后缀表示为Suffix(S,i)，也就是Suffix(S,i)=S[i..len(S)]。关于字符串的大小比较，是指通常所说的“字典顺序”比较，也就是对于两个字符串u、v，令i从1开始顺次比较u[i]和v[i]，如果u[i]=v[i]则令i加1，否则若u[i]v[i]则认为u>v（也就是vlen(u)或者i>len(v)仍比较出结果，那么若len(u)len(v)则u>v。从字符串的大小比较的定义来看，S的两个开头位置不同的后缀u和

5、v进行比较的结果不可能是相等，因为u=v的必要条件len(u)=len(v)在这里不可能满足。下面我们约定一个字符集Σ和一个字符串S，设len(S)=n，且S[n]='$'，也就是说S以一个特殊字符'$'结尾，并且'$'小于Σ中的任何一个字符。除了S[n]之外，S中的其他字符都属于Σ。对于约定的字符串S，从位置i开头的后缀直接写成Suffix(i)，省去参数S。后缀数组后缀数组SA是一个一维数组，它保存1..n的某个排列SA[1],SA[2],...SA[n]，并且保证Suffix(SA[i])

6、后把排好序的后缀的开头位置顺次放入SA中。-1名次数组名次数组Rank=SA，也就是说若SA[i]=j，则Rank[j]=i，不难看出Rank[i]保存的是Suffix(i)在所有后缀中从小到大排列的“名次”。构造方法如何构造后缀数组呢？最直接最简单的方法当然是把S的后缀都看作一些普通的字符串，按照一般字符串排序的方法对它们从小到大进行排序。不难看出，这种做法是很笨拙的，因为它没有利用到各个后缀之间的有机联系，所以它的效率不可能很高。即使采用字符串排序中比较高效的Multi-key2QuickSort，最坏情况的时间复杂度仍然是O(n)的，不能满足我们的需要。第2页共11页IO

7、I2004国家集训队论文许智磊下面介绍倍增算法(DoublingAlgorithm)，它正是充分利用了各个后缀之间的联系，将构造后缀数组的最坏时间复杂度成功降至O(nlogn)。对一个字符串u，我们定义u的k-前缀ìu[1..k],len(u)³kku=íîu,len(u)