本文共 9231 字，大约阅读时间需要 30 分钟。

【摘要】

　　后缀数组是处理字符串的有力工具。后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也并不逊色，而且它比后缀树所占用的内存空间小很多。可以说，在信息学竞赛中后缀数组比后缀树要更为实用。本文分两部分。第一部分介绍两种构造后缀数组的方法，重点介绍如何用简洁高效的代码实现，并对两种算法进行了比较。第二部分介绍后缀数组在各种类型题目中的具体应用。

　　【关键字】

　　字符串，后缀，后缀数组，名次数组，基数排序，

　　【正文】

一、后缀数组的实现

　　本节主要介绍后缀数组的两种实现方法：倍增算法（Doubling Algorithm）和DC3算法（Difference Cover），并对两种算法进行了比较。可能有的读者会认为这两种算法难以理解，即使理解了也难以用程序实现。本节针对这个问题，在介绍这两种算法的基础上，还给出了简洁高效的代码。其中倍增算法只有25行，DC3算法只有40行。

1.1、基本定义

　　子串：字符串S的子串r[i..j]，i≤j，表示r串中从i到j这一段，也就是顺次排列r[i]，r[i+1]，...，r[j]形成的字符串。

　　后缀：后缀是指从某个位置i开始到整个串末尾结束的一个特殊子串。字符串r的从第i个字符开始的后缀表示为Suffix(i)，也就是Suffix(i)=r[i..len(r)]。

　　大小比较：关于字符串的大小比较，是指通常所说的“字典顺序”比较，也就是对于两个字符串u、v，令i从1开始顺次比较u[i]和v[i]，如果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)在这里不可能满足。

　　后缀数组：后缀数组SA是一个一维数组，它保存1..n的某个排列SA[1]，SA[2]，……，SA[n]，并且保证 Suffix(SA[i])<Suffix(SA[i+1])，1≤i<n。也就是将S的n个后缀从小到大进行排序之后把排好序的后缀的开头位置顺次放入SA中。

　　名次数组：名次数组Rank[i]保存的是Suffix(i)在所有后缀中从小到大排列的“名次”。

　　简单的说，后缀数组是“排第几的是谁？”，名次数组是“你排第几？”。容易看出，后缀数组和名次数组为互逆运算。如图1所示。

　　设字符串的长度为n。为了方便比较大小，可以在字符串后面添加一个字符，这个字符没有在前面的字符中出现过，而且比前面的字符都要小。在求出名次数组后，可以仅用O(1)的时间比较任意两个后缀的大小。在求出后缀数组或名次数组中的其中一个以后，便可以用O(n)的时间求出另外一个。任意两个后缀如果直接比较大小，最多需要比较字符n次，也就是说最迟在比较第n个字符时一定能分出“胜负”。

1.2、倍增算法

　　倍增算法的主要思路是：用倍增的方法对每个字符开始的长度为2^k的子字符串进行排序，求出排名，即rank值。k从0开始，每次加1，当2^k大于n以后，每个字符开始的长度为2^k的子字符串便相当于所有的后缀。并且这些子字符串都一定已经比较出大小，即rank值中没有相同的值，那么此时的rank值就是最后的结果。每一次排序都利用上次长度为2^k-1的字符串的rank值，那么长度为2^k的字符串就可以用两个长度为2^k-1的字符串的排名作为关键字表示，然后进行基数排序，便得出了长度为2^k的字符串的rank值。以字符串“aabaaaab”为例，整个过程如图2所示。其中x、y是表示长度为2^k的字符串的两个关键字。

　　具体实现：

int wa[maxn],wb[maxn],wv[maxn],ws[maxn];

int cmp(int *r,int a,int b,int l){

return r[a]==r[b]&&r[a+l]==r[b+l];

}  //就像论文所说，由于末尾填了0，所以如果r[a]==r[b]（实际是y[a]==y[b]），说明待合并的两个长为j的字符串，前面那个一定不包含末尾0，因而后面这个的起始位置至多在0的位置，不会再靠后了，因而不会产生数组越界。

//da函数的参数n代表字符串中字符的个数，这里的n里面是包括人为在字符串末尾添加的那个0的。//da函数的参数m代表字符串中字符的取值范围，是基数排序的一个参数，如果原序列都是字母可以直接取128，如果原序列本身都是整数的话，则m可以取比最大的整数大1的值。

void da(int *r,int *sa,int n,int m){    int i,j,p,*x=wa,*y=wb,*t;    //以下四行代码是把各个字符（也即长度为1的字符串）进行基数排序    for(i=0;i
   
    =0;i--) sa[--ws[x[i]]]=i;  //i之所以从n-1开始循环，是为了保证在当字符串中有相等的字符串时，默认靠前的字符串更小一些。完成排序
   

//下面这层循环中p代表rank值不同的字符串的数量（不同字符串的个数），如果p达到n，那么各个字符串的大小关系就已经明了了。    //j代表当前待合并的字符串的长度，每次将两个长度为j的字符串合并成一个长度为2*j的字符串，当然如果包含字符串末尾，具体数值应另当别论，但思想是一样的。    //m同样代表基数排序的元素的取值范围    for(j=1,p=1;p
   
    =j) y[p++]=sa[i]-j;  //结合论文的插图，我们可以看到，下面一行的第二关键字不为0的部分都是根据上面一行的排序结果得到的，且上一行中只有sa[i]>=j的第sa[i]个字符串（这里以及后面指的“第?个字符串”不是按字典序排名来的，是按照首字符在字符串中的位置来的）的rank才会作为下一行的第sa[i]-j个字符串的第二关键字，而且显然按sa[i]的顺序rank[sa[i]]是递增的，因此完成了对剩余的元素的第二关键字的排序。        //第二关键字基数排序完成后，y[]里存放的是按第二关键字排序的字符串下标
   

for(i=0;i
   
    =0;i--) sa[--ws[wv[i]]]=y[i];  //i之所以从n-1开始循环，含义同上，同时注意这里是y[i]，因为y[i]里面才存着字符串的下标        
   

//下面两行就是计算合并之后的rank值了，而合并之后的rank值应该存在x[]里面，但我们计算的时候又必须用到上一层的rank值，也就是现在x[]里面放的东西，如果我既要从x[]里面拿，又要向x[]里面放，怎么办？当然是先把x[]的东西放到另外一个数组里面，省得乱了。这里就是用交换指针的方式，高效实现了将x[]的东西“复制”到了y[]中。

for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i

//height 数组：定义height[i]=suffix(sa[i-1])和suffix(sa[i])的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀。 //height数组是应用后缀数组解题是的核心，基本上使用后缀数组解决的题目都是依赖height数组完成的。//能够线性计算height[]的值的关键在于h[](height[rank[]])的性质，即h[i]>=h[i-1]-1，下面具体分析一下这个不等式的由来。//论文里面证明的部分一开始看得我云里雾里，后来画了一下终于搞明白了，我们先把要证什么放在这：对于第i个后缀，设j=sa[rank[i] - 1]，也就是说j是i的按排名来的上一个字符串，按定义来i和j的最长公共前缀就是height[rank[i]]，我们现在就是想知道height[rank[i]]至少是多少，而我们要证明的就是至少是height[rank[i-1]]-1。//好啦，现在开始证吧。//首先我们不妨设第i-1个字符串（这里以及后面指的“第?个字符串”不是按字典序排名来的，是按照首字符在字符串中的位置来的）按字典序排名来的前面的那个字符串是第k个字符串，注意k不一定是i-2，因为第k个字符串是按字典序排名来的i-1前面那个，并不是指在原字符串中位置在i-1前面的那个第i-2个字符串。//这时，依据height[]的定义，第k个字符串和第i-1个字符串的公共前缀自然是height[rank[i-1]]，现在先讨论一下第k+1个字符串和第i个字符串的关系。//第一种情况，第k个字符串和第i-1个字符串的首字符不同，那么第k+1个字符串的排名既可能在i的前面，也可能在i的后面，但没有关系，因为height[rank[i-1]]就是0了呀，那么无论height[rank[i]]是多少都会有height[rank[i]]>=height[rank[i-1]]-1，也就是h[i]>=h[i-1]-1。//第二种情况，第k个字符串和第i-1个字符串的首字符相同，那么由于第k+1个字符串就是第k个字符串去掉首字符得到的，第i个字符串也是第i-1个字符串去掉首字符得到的，那么显然第k+1个字符串要排在第i个字符串前面，要么就产生矛盾了。同时，第k个字符串和第i-1个字符串的最长公共前缀是height[rank[i-1]]，那么自然第k+1个字符串和第i个字符串的最长公共前缀就是height[rank[i-1]]-1。//到此为止，第二种情况的证明还没有完，我们可以试想一下，对于比第i个字符串的字典序排名更靠前的那些字符串，谁和第i个字符串的相似度最高（这里说的相似度是指最长公共前缀的长度）？显然是排名紧邻第i个字符串的那个字符串了呀，即sa[rank[i]-1]。也就是说sa[rank[i]]和sa[rank[i]-1]的最长公共前缀至少是height[rank[i-1]]-1，那么就有height[rank[i]]>=height[rank[i-1]]-1，也即h[i]>=h[i-1]-1。//证明完这些之后，下面的代码也就比较容易看懂了。int rank[maxn],height[maxn];void calheight(int *r,int *sa,int n){    int i,j,k=0;    for(i=1;i<=n;i++) rank[sa[i]]=i;  //计算每个字符串的字典序排名,i从1开始是因为排名为零的字符串为最后添加的字符（防越界用的）    for(i=0;i

                         二、后缀数组的应用

2.1、最长公共前缀

给定一个字符串，询问某两个后缀的最长公共前缀。

　　算法分析：

　　按照上面所说的做法，求两个后缀的最长公共前缀可以转化为求某个区间上的最小值。对于这个RMQ问题（如果对RMQ（Range Minimum Query）问题不熟悉，请阅读其他相关资料），可以用O(nlogn)的时间先预处理，以后每次回答询问的时间为O(1)。所以对于本问题，预处理时间为O(nlogn)，每次回答询问的时间为O(1)。如果RMQ问题用O(n)的时间预处理，那么本问题预处理的时间可以做到O(n)。

suffix(j) 和suffix(k) 的最长公共前缀为height[rank[j]+1], height[rank[j]+2], height[rank[j]+3], … ,height[rank[k]]中的最小值。求两个后缀的最长公共前缀可以转化为求某个区间上的最小值。

2.2、单个字符串的相关问题

　　这类问题的一个常用做法是先求后缀数组和 height数组，然后利用 height数组进行求解。

2.2.1、重复子串

　　重复子串：字符串R在字符串L中至少出现两次，则称R是L的重复子串。

　　例2：可重叠最长重复子串

　　给定一个字符串，求最长重复子串，这两个子串可以重叠。

　　算法分析：

　　这道题是后缀数组的一个简单应用。做法比较简单，只需要求height数组里的最大值即可。首先求最长重复子串，等价于求两个后缀的最长公共前缀的最大值。因为任意两个后缀的最长公共前缀都是height数组里某一段的最小值，那么这个值一定不大于height数组里的最大值。所以最长重复子串的长度就是height数组里的最大值。这个做法的时间复杂度为O(n)。

　　例3：不可重叠最长重复子串（pku1743）

　　给定一个字符串，求最长重复子串，这两个子串不能重叠。

　　算法分析：

　　这题比上一题稍复杂一点。先二分答案，把题目变成判定性问题：判断是否存在两个长度为k的子串是相同的，且不重叠。解决这个问题的关键还是利用height数组。把排序后的后缀分成若干组，其中每组的后缀之间的height值都不小于k。例如，字符串为“aabaaaab”，当 k=2时，后缀分成了 4组，如图5所示。

　　容易看出，有希望成为最长公共前缀不小于k的两个后缀一定在同一组。然后对于每组后缀，只须判断每个后缀的sa值的最大值和最小值之差是否不小于k。如果有一组满足，则说明存在，否则不存在。整个做法的时间复杂度为O(nlogn)。本题中利用 height值对后缀进行分组的方法很常用，请读者认真体会。

　　例4：可重叠的 k次最长重复子串（pku3261）

　　给定一个字符串，求至少出现k次的最长重复子串，这k个子串可以重叠。

　　算法分析：

　　这题的做法和上一题差不多，也是先二分答案，然后将后缀分成若干组。不同的是，这里要判断的是有没有一个组的后缀个数不小于k。如果有，那么存在k个相同的子串满足条件，否则不存在。这个做法的时间复杂度为 O(nlogn)。

2.2.2、子串的个数

　　例5：不相同的子串的个数（spoj694，spoj705）

　　给定一个字符串，求不相同的子串的个数。

　　算法分析：

　　每个子串一定是某个后缀的前缀，那么原问题等价于求所有后缀之间的不相同的前缀的个数。如果所有的后缀按照suffix(sa[1])，suffix(sa[2])，suffix(sa[3])，……，suffix(sa[n])的顺序计算，不难发现，对于每一次新加进来的后缀suffix(sa[k])，它将产生n-sa[k]+1个新的前缀。但是其中有height[k]个是和前面的字符串的前缀是相同的。所以suffix(sa[k])将“贡献”出n-sa[k]+1-height[k]个不同的子串。累加后便是原问题的答案。这个做法的时间复杂度为O(n)。

2.2.3、回文子串

　　回文子串：如果将字符串L的某个子字符串R反过来写后和原来的字符串R一样，则称字符串R是字符串L的回文子串。

　　例6：最长回文子串（ural1297）

　　给定一个字符串，求最长回文子串。

　　算法分析：

　　穷举每一位，然后计算以这个字符为中心的最长回文子串。注意这里要分两种情况，一是回文子串的长度为奇数，二是长度为偶数。两种情况都可以转化为求一个后缀和一个反过来写的后缀的最长公共前缀。具体的做法是：将整个字符串反过来写在原字符串后面，中间用一个特殊的字符隔开。这样就把问题变为了求这个新的字符串的某两个后缀的最长公共前缀。如图6所示。

　　这个做法的时间复杂度为O(nlogn)。如果RMQ问题用时间为O(n)的方法预处理，那么本题的时间复杂度可以降为O(n)。

2.2.4、连续重复子串

　　连续重复串：如果一个字符串L是由某个字符串S重复R次而得到的，则称L是一个连续重复串。R是这个字符串的重复次数。

　　例7：连续重复子串（pku2406）

　　给定一个字符串L，已知这个字符串是由某个字符串S重复R次而得到的，求R的最大值。

　　算法分析：

　　做法比较简单，穷举字符串S的长 k，然后判断是否满足。判断的时候，先看字符串L的长度能否被k整除，再看suffix(1)和suffix(k+1)的最长公共前缀是否等于n-k。在询问最长公共前缀的时候，suffix(1)是固定的，所以RMQ问题没有必要做所有的预处理，只需求出height数组中的每一个数到height[rank[1]]之间的最小值即可。整个做法的时间复杂度为O(n)。

　　例8：重复次数最多的连续重复子串（spoj687，pku3693）

　　给定一个字符串，求重复次数最多的连续重复子串。

　　算法分析：

　　先穷举长度L，然后求长度为L的子串最多能连续出现几次。首先连续出现1次是肯定可以的，所以这里只考虑至少2次的情况。假设在原字符串中连续出现2次，记这个子字符串为S，那么S肯定包括了字符r[0]，r[L]，r[L*2]，r[L*3]，……中的某相邻的两个。所以只须看字符r[L*i]和r[L*(i+1)]往前和往后各能匹配到多远，记这个总长度为K，那么这里连续出现了K/L+1次。最后看最大值是多少。如图7所示。

　　穷举长度L的时间是n，每次计算的时间是n/L。所以整个做法的时间复杂度是O(n/1+n/2+n/3+……+n/n)=O(nlogn)。

2.3、两个字符串的相关问题

　　这类问题的一个常用做法是，先连接这两个字符串，然后求后缀数组和height数组，再利用height数组进行求解。

2.3.1、公共子串

　　公共子串：如果字符串L同时出现在字符串A和字符串B中，则称字符串L是字符串A和字符串B的公共子串。

　　例9：最长公共子串（pku2774，ural1517）

　　给定两个字符串A和B，求最长公共子串。

　　算法分析:

　　字符串的任何一个子串都是这个字符串的某个后缀的前缀。求A和B的最长公共子串等价于求A的后缀和B的后缀的最长公共前缀的最大值。如果枚举A和B的所有的后缀，那么这样做显然效率低下。由于要计算A的后缀和B的后缀的最长公共前缀，所以先将第二个字符串写在第一个字符串后面，中间用一个没有出现过的字符隔开，再求这个新的字符串的后缀数组。观察一下，看看能不能从这个新的字符串的后缀数组中找到一些规律。以A=“aaaba”，B=“abaa”为例，如图8所示。

　　那么是不是所有的height值中的最大值就是答案呢？不一定！有可能这两个后缀是在同一个字符串中的，所以实际上只有当suffix(sa[i-1])和suffix(sa[i])不是同一个字符串中的两个后缀时，height[i]才是满足条件的。而这其中的最大值就是答案。记字符串A和字符串B的长度分别为|A|和|B|。求新的字符串的后缀数组和height数组的时间是O(|A|+|B|)，然后求排名相邻但原来不在同一个字符串中的两个后缀的height值的最大值，时间也是O(|A|+|B|)，所以整个做法的时间复杂度为O(|A|+|B|)。时间复杂度已经取到下限，由此看出，这是一个非常优秀的算法。

2.3.2、子串的个数

　　例10：长度不小于k的公共子串的个数（pku3415）

　　给定两个字符串A和B，求长度不小于k的公共子串的个数（可以相同）。

　　样例1：

　　A=“xx”，B=“xx”，k=1，长度不小于k的公共子串的个数是5。

　　样例2：

　　A =“aababaa”，B =“abaabaa”，k=2，长度不小于k的公共子串的个数是22。

　　算法分析：

　　基本思路是计算A的所有后缀和B的所有后缀之间的最长公共前缀的长度，把最长公共前缀长度不小于k的部分全部加起来。先将两个字符串连起来，中间用一个没有出现过的字符隔开。按height值分组后，接下来的工作便是快速的统计每组中后缀之间的最长公共前缀之和。扫描一遍，每遇到一个B的后缀就统计与前面的A的后缀能产生多少个长度不小于k的公共子串，这里A的后缀需要用一个单调的栈来高效的维护。然后对A也这样做一次。具体的细节留给读者思考。

2.4、多个字符串的相关问题

　　这类问题的一个常用做法是，先将所有的字符串连接起来，然后求后缀数组和height数组，再利用height数组进行求解。这中间可能需要二分答案。

　　例11：不小于k个字符串中的最长子串（pku3294）

　　给定n个字符串，求出现在不小于k个字符串中的最长子串。

　　算法分析：

　　将n个字符串连起来，中间用不相同的且没有出现在字符串中的字符隔开，求后缀数组。然后二分答案，用和例3同样的方法将后缀分成若干组，判断每组的后缀是否出现在不小于k个的原串中。这个做法的时间复杂度为O(nlogn)。

　　例12：每个字符串至少出现两次且不重叠的最长子串（spoj220）

　　给定n个字符串，求在每个字符串中至少出现两次且不重叠的最长子串。

　　算法分析：

　　做法和上题大同小异，也是先将n个字符串连起来，中间用不相同的且没有出现在字符串中的字符隔开，求后缀数组。然后二分答案，再将后缀分组。判断的时候，要看是否有一组后缀在每个原来的字符串中至少出现两次，并且在每个原来的字符串中，后缀的起始位置的最大值与最小值之差是否不小于当前答案（判断能否做到不重叠，如果题目中没有不重叠的要求，那么不用做此判断）。这个做法的时间复杂度为 O(nlogn)。

　　例13：出现或反转后出现在每个字符串中的最长子串（PKU3294）

　　给定n个字符串，求出现或反转后出现在每个字符串中的最长子串。

　　算法分析：

　　这题不同的地方在于要判断是否在反转后的字符串中出现。其实这并没有加大题目的难度。只需要先将每个字符串都反过来写一遍，中间用一个互不相同的且没有出现在字符串中的字符隔开，再将n个字符串全部连起来，中间也是用一个互不相同的且没有出现在字符串中的字符隔开，求后缀数组。然后二分答案，再将后缀分组。判断的时候，要看是否有一组后缀在每个原来的字符串或反转后的字符串中出现。这个做法的时间复杂度为O(nlogn)。

http://www.cppblog.com/superKiki/archive/2010/05/15/115421.html

http://www.cnblogs.com/staginner/archive/2012/02/02/2335600.html