2.4　后缀数组

前面曾经提到过Aho-Corasick自动机算法，用以解决多模板匹配问题。其前提是需要事先知道所有的模板，但在实际应用中，无法事先知道查询内容，比如在搜索引擎中，每次的查询是不可能直接预处理出来的，这就需要预处理文本串而非每次的查询内容。

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

2.4.1　后缀数组基本原理

首先定义两个概念：

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

（2）名次数组：名次数组rank[i]保存的是suffix（i）在所有后缀中从小到大排列的“名次”，如图2.9所示。

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

设字符串的长度为n，为了方便比较大小，可以在字符串后面添加一个字符，这个字符没有在前面的字符中出现过，而且比前面的字符都要小。在求出名次数组后，可以仅用O（1）的时间比较任意两个后缀的大小。在求出后缀数组或名次数组中的其中一个后，便可以用O（n）的时间求出另外一个。

下面介绍一种常用的用来实现后缀数组的倍增算法。

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

后缀数组倍增算法的实现如下所述。

待排序的字符串放在r数组中，从r[0]到r[n-1]，长度为n，且最大值小于m。为了函数操作的方便，约定除r[n-1]外的所有r[i]都大于0，r[n-1]=0。函数结束后，结果放在sa数组中，从sa[0]到sa[n-1]。

函数的第一步，要对长度为1的字符串进行排序。一般来说，在字符串的题目中，r的最大值不会很大，所以使用了基数排序。如果r的最大值很大，那么就把这段代码改成快速排序。代码如下所述。

x数组保存的值相当于是rank值。下面的操作只是用x数组比较字符的大小，所以没有必要求出当前真实的rank值。

接下来进行若干次基数排序，在实现的时候，有一个优化。基数排序要分两次，第一次是对第二关键字排序，第二次是对第一关键字排序。对第二关键字排序的结果实际上可以利用上一次求得的sa直接算出，没有必要再算一次，其代码如下所述。

其中，变量j是当前字符串的长度，数组y保存的是对第二关键字排序的结果，然后对第一关键字进行排序，其代码如下所述。

这样求出了新的sa值。在求出sa值后，下一步是计算rank值。要注意的是，可能有多个字符串的rank值是相同的，所以必须比较两个字符串是否完全相同，y数组的值已经没有必要保存，为了节省空间，用y数组保存rank值。有一个优化，将x和y定义为指针类型，复制整个数组的操作可以用交换指针的值代替，不必逐个地复制数组中的值，其代码如下所述。

其中，cmp函数的代码如下。

规定r[n-1]=0的优点在于如果r[a]=r[b]，说明以r[a]或r[b]开头的长度为l的子串肯定不包括r[n-1]，所以调用变量r[a+l]和r[b+l]不会导致数组下标越界，就不需要做特殊判断。执行完上面的代码后，rank值保存在x数组中，而变量p的结果实际上就是不同的子串的个数。可以优化，如果p等于n，那么函数可以结束。因为在当前长度的字符串中，已经没有相同的字符串，接下来的排序不会改变rank值。对上面的两段代码，循环的初始赋值和终止条件如下所述。

在第一次排序以后，rank数组中的最大值小于p，所以令m=p。整个倍增算法基本写好，代码大约25行。倍增算法的时间复杂度为每次基数排序的时间复杂度O（n），排序的次数取决于最长公共子串的长度。最坏的情况下，排序次数为logn次，所以总的时间复杂度为O（nlogn）。

2.4.2　后缀数组的应用

先介绍后缀数组的一些性质。

height数组：定义height[i]=suffix（sa[i-1]）和suffix（sa[i]）的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀。那么对于j和k，不妨设rank[j]<rank[k]，则有以下性质。

suffix（j）和suffix（k）的最长公共前缀为height[rank[j]+1]，height[rank[j]+2]，height[rank[j]+3]，…，height[rank[k]]中的最小值。

例如，字符串为“aabaaaab”，求后缀“abaaaab”和后缀“aaab”的最长公共前缀，如图2.11所示。

那么应该如何高效地求出height值呢？

如果按height[2]，height[3]，…，height[n]的顺序计算，最坏情况下的时间复杂度为O（n2），而没有利用字符串的性质。定义h[i]=height[rank[i]]，也就是suffix（i）和在它前一名的后缀的最长公共前缀。

h[]数组有以下性质：h[i]≥h[i-1]-1。

证明：设suffix（k）是排在suffix（i-1）前一名的后缀，则它们的最长公共前缀是h[i-1]。那么suffix（k+1）将排在suffix（i）的前面（要求h[i-1]>1，如果h[i-1]≤1，原式显然成立），并且suffix（k+1）和suffix（i）的最长公共前缀是h[i-1]-1，所以suffix（i）和在它前一名的后缀的最长公共前缀至少是h[i-1]-1。按照h[1],h[2],…,h[n]的顺序计算，并利用h数组的性质，时间复杂度可以降为O（n）。

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

算法分析：按照上面所说的做法，求两个后缀的最长公共前缀可以转化为求某个区间上的最小值。对于这个RMQ（Range Minimum Query）问题，可以用O（nlogn）的时间先预处理，以后每次回答询问的时间复杂度为O（1）。所以预处理的时间复杂度为O（nlogn），每次回答询问的时间复杂度为O（1）。如果RMQ问题用O（n）的时间复杂度预处理，那么本问题预处理的时间复杂度可以做到O（n）。

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

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

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

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

容易看出，有希望成为最长公共前缀且不小于k的两个后缀一定在同一组中。对于每组的后缀，只需要判断每个后缀的sa值的最大值和最小值之差是否不小于k。如果有一组满足，则说明存在，否则不存在。算法的时间复杂度为O（nlogn）。本题中利用height值对后缀进行分组的方法很常用。

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

算法分析：先二分答案，然后将后缀分成若干组，判断有没有一个组的后缀个数不小于k。如果有，那么存在k个相同的子串满足条件，否则不存在。算法的时间复杂度为O（nlogn）。

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

算法分析：每个子串一定是某个后缀的前缀，那么原问题等价于求所有后缀之间的不相同的前缀的个数。如果所有的后缀按照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.4.3　例题讲解

例2-4　Distinct Substrings

Time Limit:2000/1000 ms（Java/Others）　Memory Limit:131072/131072 KB（Java/Others）

题目描述：

给定一个字符串，需要找出所有的不同的子串。

输入：

第一行输入测试数据T（≤20）组，接下来在每行中包括一个字符串（字符串长度不超过1000）。

输出：

对于每组数据，都要输出一行，并包含一个整数，该整数表示该字符串有多少个不同的子串。

样例输入：

2

CCCCC

ABABA

样例输出：

5

9

题目来源：SPO J694。

解题思路：

一个字符串中不同子串的总数为∑（len-height[i]-sa[i]）。

题目实现：

例2-5　Musical Theme

Time Limit:2000/1000 ms（Java/Others）　Memory Limit:131072/131072 KB（Java/Others）

题目描述：

用N（1≤N≤20000）个音符的序列来表示一首乐曲，每个音符都是1～88范围内的整数，现在要找一个重复的主题。主题是整个音符序列的一个子串，需要满足如下条件：

（1）长度至少为5个音符。

（2）在乐曲中重复出现（可能经过转调，转调的意思是在主题序列的每个音符上都加上或减去同一个整数值）。

（3）重复出现的同一主题不能有公共部分，即给出一串字符，求不重合的最长重复子串，并且长度大于要求的5。

输入：

输入数据有多组，每组数据的第一行输入一个整数N，在接下来一行中的N个整数表示音符序列，最后一组测试数据以0结束。

输出：

对于每组数据，都要输出一行并包含一个整数，该整数表示该字符串满足条件的最长重复子串长度。

样例输入：

30

25 27 30 34 39 45 52 60 69 79 69 60 52 45 39 34 30 26 22 18

82 78 74 70 66 67 64 60 65 80

0

样例输出：

5

题目来源：POJ 1743。

解题思路：

将height值分组，然后记录在二分答案时满足height值不小于p的sa[i]的最大、最小值，如果最大值减去最小值不小于p，就说明两个子串的lcp值不小于p，并且它们的坐标也相差不小于p。另外，转调的影响可通过求相邻序列的差值解决。

题目实现：