论文--后缀数组.doc

后缀数组【作者】安徽省芜湖市第一中学许智磊【摘要】本文介绍后缀数组的基本概念、方法以及应用。首先介绍O(nlogn)复杂度构造后缀数组的倍增算法,接着介绍了配合后缀数组的最长公共前缀LCP(monPrefix)的计算方法,并给出一个线性时间内计算height数组(记录跨度为1的LCP值的数组)的算法。最后介绍两个应用后缀数组的例子:多模式串的模式匹配以及求最长回文子串。【关键字】字符串后缀 k-前缀比较关系后缀数组名次数组后缀树倍增算法基数排序最长公共前缀 RMQ问题模式匹配回文串最长回文子串【正文】在字符串处理当中,后缀树和后缀数组都是非常有力的工具,其中后缀树大家了解得比较多,关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品,它比后缀树容易编程实现,能够实现后缀树的很多功能而时间复杂度也不太逊色,并且,它比后缀树所占用的空间小很多。可以说,在信息学竞赛中后缀数组比后缀树要更为实用。因此在本文中笔者想介绍一下后缀数组的基本概念、构造方法,以及配合后缀数组的最长公共前缀数组的构造方法,最后结合一些例子谈谈后缀数组的应用。基本概念首先明确一些必要的定义:字符集一个字符集Σ是一个建立了全序关系的集合,也就是说,Σ中的任意两个不同的元素α和β都可以比较大小,要么α<β,要么β<α(也就是α>β)。字符集Σ中的元素称为字符。字符串一个字符串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开头的后缀表示为Suffix(S,i),也就是Suffix(S,i)=S[i..len(S)]。关于字符串的大小比较,是指通常所说的“字典顺序”比较,也就是对于两个字符串u、v,令i从1开始顺次比较u[i]和v[i],如果相等则令i加1,否则若u[i]<v[i]则认为u<v,u[i]>v[i]则认为u>v(也就是v<u),比较结束。如果i>len(u)或者i>len(v)仍比较出结果,那么若len(u)<len(v)则认为u<v,若len(u)=len(v)则认为u=v,若len(u)>len(v)则u>v。从字符串的大小比较的定义来看,S的两个开头位置不同的后缀u和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])<Suffix(SA[i+1]),1≤i<n。也就是将S的n个后缀从小到大进行排序之后把排好序的后缀的开头位置顺次放入SA中。名次数组名次数组Rank=SA-1,也就是说若SA[i]=j,则Rank[j]=i,不难看出Rank[i]保存的