IOI2004 国家集训队论文 许智磊
第 1 页 共 11 页
后 缀 数 组
安徽省芜湖市第一中学 许智磊
【摘要】
本文介绍后缀数组的基本概念、方法以及应用。
首先介绍 O(nlogn)复杂度构造后缀数组的倍增算法，接着介绍了配合后缀
数组的最长公共前缀 LCP（Longest Common Prefix）的计算方法，并给出一个
线性时间内计算 height 数组（记录跨度为 1 的 LCP 值的数组）的算法。为了让
读者对如何运用后缀数组有一个感性认识，还介绍了两个应用后缀数组的例子：
多模式串的模式匹配（给出每次匹配 O(m+logn)时间复杂度的算法）以及求最
长回文子串（给出 O(nlogn)时间复杂度的算法）。最后对后缀数组和后缀树作了
一番比较。
【关键字】
字符串 后缀 k-前缀比较关系
后缀数组 名次数组 后缀树 倍增算法 基数排序
最长公共前缀 RMQ 问题 模式匹配 回文串 最长回文子串
【正文】
在字符串处理当中，后缀树和后缀数组都是非常有力的工具，其中后缀树
大家了解得比较多，关于后缀数组则很少见于国内的资料。其实后缀数组是后
缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的
很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。
可以说，在信息学竞赛中后缀数组比后缀树要更为实用。因此在本文中笔者想
介绍一下后缀数组的基本概念、构造方法，以及配合后缀数组的最长公共前缀
数组的构造方法，最后结合一些例子谈谈后缀数组的应用。
IOI2004 国家集训队论文 许智磊
第 2 页 共 11 页
基本概念
首先明确一些必要的定义：
字符集 一个字符集Σ是一个建立了全序关系的集合，也就是说，Σ中
的任意两个不同的元素 α 和 β 都可以比较大小，要么 α<β，要么 β<α（也就是
α>β）。 字符集Σ中的元素称为字符。
字符串 一个字符串 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]，如果 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]保存的是 Suffix(i)在所有后缀中从小到大排列的“名次”。
构造方法
如何构造后缀数组呢？最直接最简单的方法当然是把 S 的后缀都看作一些
普通的字符串，按照一般字符串排序的方法对它们从小到大进行排序。
不难看出，这种做法是很笨拙的，因为它没有利用到各个后缀之间的有机
联系，所以它的效率不可能很高。即使采用字符串排序中比较高效的 Multi-key
Quick Sort，最坏情况的时间复杂度仍然是 O(n
2
)的，不能满足我们的需要。
IOI2004 国家集训队论文 许智磊
第 3 页 共 11 页
下面介绍倍增算法(Doubling Algorithm)，它正是充分利用了各个后缀之间的
联系，将构造后缀数组的最坏时间复杂度成功降至 O(nlogn)。
对一个字符串 u，我们定义 u 的 k-前缀
<
≥
=
kulenu
kulenku
u
k
)(,
)(,]..1[
定义 k-前缀比较关系<
k
、=
k
和≤
k
：
设两个字符串 u 和 v，
u<
k
v 当且仅当 u
k
<v
k
u=
k
v 当且仅当 u
k
=v
k
u≤
k
v 当且仅当 u
k
≤v
k
直观地看这些加了一个下标 k 的比较符号的意义就是对两个字符串的前 k
个字符进行字典序比较，特别的一点就是在作大于和小于的比较时如果某个字
符串的长度不到 k 也没有关系，只要能够在 k 个字符比较结束之前得到第一个
字符串大于或者小于第二个字符串就可以了。
根据前缀比较符的性质我们可以得到以下的非常重要的性质：
性质 1.1 对 k≥n，Suffix(i)<
k
Suffix(j) 等价于 Suffix(i)<Suffix(j)。
性质 1.2 Suffix(i)=
2k
Suffix(j)等价于
Suffix(i)=
k
Suffix(j) 且 Suffix(i+k)=
k
Suffix(j+k)。
性质 1.3 Suffix(i)<
2k
Suffix(j) 等价于
Suffix(i)<
k
S(j) 或 (Suffix(i)=
k
Suffix(j) 且 Suffix(i+k)<
k
Suffix(j+k))。
这里有一个问题，当 i+k>n 或者 j+k>n 的时候 Suffix(i+k)或 Suffix(j+k)是无
明确定义的表达式，但实际上不需要考虑这个问题，因为此时 Suffix(i)或者
Suffix(j)的长度不超过 k，也就是说它们的 k-前缀以'$'结尾，于是 k-前缀比较的
结果不可能相等，也就是说前 k 个字符已经能够比出大小，后面的表达式自然
可以忽略，这也就看出我们规定 S 以'$'结尾的特殊用处了。
定义 k-后缀数组 SA
k
保存 1..n 的某个排列 SA
k
[1],SA
k
[2],…SA
k
[n]使得
Suffix(SA
k
[i]) ≤
k
Suffix(SA
k
[i+1]),1≤i<n。也就是说对所有的后缀在 k-前缀比较关
系下从小到大排序，并且把排序后的后缀的开头位置顺次放入数组 SA
k
中。
定义 k-名次数组 Rank
k
，Rank
k
[i]代表 Suffix(i)在 k-前缀关系下从小到大的
“名次”，也就是 1 加上满足 Suffix(j)<
k
Suffix(i)的 j 的个数。通过 SA
k
很容易在
O(n)的时间内求出 Rank
k
。
假设我们已经求出了 SA
k
和 Rank
k
，那么我们可以很方便地求出 SA
2k
和
Rank
2k
，因为根据性质 1.2 和 1.3，2k-前缀比较关系可以由常数个 k-前缀比较关
系组合起来等价地表达，而 Rank
k
数组实际上给出了在常数时间内进行<
k
和=
k
比较的方法，即：
Suffix(i)<
k
Suffix(j) 当且仅当 Rank
k
[i]<Rank
k
[j]
Suffix(i)=
k
Suffix(j) 当且仅当 Rank
k
[i]=Rank
k
[j]
因此，比较 Suffix(i)和 Suffix(j)在 k-前缀比较关系下的大小可以在常数时间
内完成，于是对所有的后缀在≤
k
关系下进行排序也就和一般的排序没有什么区
别了，它实际上就相当于每个 Suffix(i)有一个主关键字 Rank
k
[i]和一个次关键字
Rank
k
[i+k]。如果采用快速排序之类 O(nlogn)的排序，那么从 SA
k
和 Rank
k
构造
IOI2004 国家集训队论文 许智磊
第 4 页 共 11 页
出 SA
2k
的复杂度就是 O(nlogn)。更聪明的方法是采用基数排序，复杂度为 O(n)。
求出 SA
2k
之后就可以在 O(n)的时间内根据 SA
2k
构造出 Rank
2k
。因此，从 SA
k
和 Rank
k
推出 SA
2k
和 Rank
2k
可以在 O(n)时间内完成。
下面只有一个问题需要解决：如何构造出 SA
1
和 Rank
1
。这个问题非常简单：
因为<
1
，=
1
和≤
1
这些运算符实际上就是对字符串的第一个字符进行比较，所以
只要把每个后缀按照它的第一个字符进行排序就可以求出 SA
1
，不妨就采用快
速排序，复杂度为 O(nlogn)。
于是，可以在 O(nlogn)的时间内求出 SA
1
和 Rank
1
。
求出了 SA
1
和 Rank
1
，我们可以在 O(n)的时间内求出 SA
2
和 Rank
2
，同样，
我们可以再用 O(n)的时间求出 SA
4
和 Rank
4
，这样，我们依次求出：
SA
2
和 Rank
2
，SA
4
和 Rank
4
，SA
8
和 Rank
8
，……直到 SA
m
和 Rank
m
，其中
m=2
k
且 m≥n。而根据性质 1.1，SA
m
和 SA 是等价的。这样一共需要进行 logn
次 O(n)的过程，因此
可以在 O(nlogn)的时间内计算出后缀数组 SA 和名次数组 Rank。
最长公共前缀
现在一个字符串 S 的后缀数组 SA 可以在 O(nlogn)的时间内计算出来。利用
SA 我们已经可以做很多事情，比如在 O(mlogn)的时间内进行模式匹配，其中
m,n 分别为模式串和待匹配串的长度。但是要想更充分地发挥后缀数组的威力，
我们还需要计算一个辅助的工具——最长公共前缀（Longest Common Prefix）。
对两个字符串 u,v 定义函数 lcp(u,v)=max{i|u=
i
v}，也就是从头开始顺次比较
u 和 v 的对应字符，对应字符持续相等的最大位置，称为这两个字符串的最长
公共前缀。
对正整数 i,j 定义 LCP(i,j)=lcp(Suffix(SA[i]),Suffix(SA[j])，其中 i,j 均为 1 至
n 的整数。LCP(i,j)也就是后缀数组中第 i 个和第 j 个后缀的最长公共前缀的长
度。
关于 LCP 有两个显而易见的性质：
性质 2.1 LCP(i,j)=LCP(j,i)
性质 2.2 LCP(i,i)=len(Suffix(SA[i]))=n-SA[i]+1
这两个性质的用处在于，我们计算 LCP(i,j)时只需要考虑 i<j 的情况，因为
i>j 时可交换 i,j，i=j 时可以直接输出结果 n-SA[i]+1。
直接根据定义，用顺次比较对应字符的方法来计算 LCP(i,j)显然是很低效
的，时间复杂度为 O(n)，所以我们必须进行适当的预处理以降低每次计算 LCP
的复杂度。
经过仔细分析，我们发现 LCP 函数有一个非常好的性质：
设 i<j，则 LCP(i,j)=min{LCP(k-1,k)|i+1≤k≤j} （LCP Theorem）
要证明 LCP Theorem，首先证明 LCP Lemma:
对任意 1≤i<j<k≤n，LCP(i,k)=min{LCP(i,j),LCP(j,k)}
证明：设 p=min{LCP(i,j),LCP(j,k)}，则有 LCP(i,j)≥p,LCP(j,k)≥p。
