后缀数组简介

一些约定

字符串相关的定义请参考

字符串基础。

字符串下标从 开始。

字符串 的长度为 。

" 后缀 " 代指以第 个字符开头的后缀，存储时用 代表字符串 的后缀 。

后缀数组是什么？

后缀数组（Suffix Array）主要关系到两个数组： 和 。

其中， 表示将所有后缀排序后第 小的后缀的编号，也是所说的后缀数组，后文也称编号数组 ；

表示后缀 的排名，是重要的辅助数组，后文也称排名数组 。

这两个数组满足性质：。

解释

后缀数组示例：

后缀数组怎么求？

O(n^2logn) 做法

我相信这个做法大家还是能自己想到的：将盛有全部后缀字符串的数组进行 sort 排序，由于排序进行 次字符串比较，每次字符串比较要 次字符比较，所以这个排序是 的时间复杂度。

O(nlog^2n) 做法

这个做法要用到倍增的思想。

首先对字符串 的所有长度为 的子串，即每个字符进行排序，得到排序后的编号数组 和排名数组 。

倍增过程：

1. 用两个长度为 的子串的排名，即 和 ，作为排序的第一第二关键字，就可以对字符串 的每个长度为 的子串： 进行排序，得到 和 ；

2. 之后用两个长度为 的子串的排名，即 和 ，作为排序的第一第二关键字，就可以对字符串 的每个长度为 的子串： 进行排序，得到 和 ；

3. 以此倍增，用长度为 的子串的排名，即 和 ，作为排序的第一第二关键字，就可以对字符串 的每个长度为 的子串 进行排序，得到 和 。其中，类似字母序排序规则，当 时， 视为无穷小；

4. 即是子串 的排名，这样当 时，得到的编号数组 ，也就是我们需要的后缀数组。

过程

倍增排序示意图：

显然倍增的过程是 ，而每次倍增用 sort 对子串进行排序是 ，而每次子串的比较花费 次字符比较；

除此之外，每次倍增在 sort 排序完后，还有额外的 时间复杂度的，更新 的操作，但是相对于 被忽略不计；

所以这个算法的时间复杂度就是 。

O(nlogn) 做法

在刚刚的 做法中，单次排序是 的，如果能 排序，就能 计算后缀数组了。

前置知识：

计数排序，

基数排序。

由于计算后缀数组的过程中排序的关键字是排名，值域为 ，并且是一个双关键字的排序，可以使用基数排序优化至 。

一些常数优化

如果你把上面那份代码交到 LOJ #111: 后缀排序 上：

这是因为，上面那份代码的常数的确很大。

第二关键字无需计数排序

思考一下第二关键字排序的实质，其实就是把超出字符串范围（即 ）的 放到 数组头部，然后把剩下的依原顺序放入：

优化计数排序的值域

每次对 进行更新之后，我们都计算了一个 ，这个 即是 的值域，将值域改成它即可。

将 rk[id[i]] 存下来，减少不连续内存访问

这个优化在数据范围较大时效果非常明显。

用函数 cmp 来计算是否重复

同样是减少不连续内存访问，在数据范围较大时效果比较明显。

把 oldrk[sa[i]] == oldrk[sa[i - 1]] && oldrk[sa[i] + w] == oldrk[sa[i - 1] + w]

替换成 cmp(sa[i], sa[i - 1], w)，

bool cmp(int x, int y, int w) { return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w]; }。

若排名都不相同可直接生成后缀数组

考虑新的 数组，若其值域为 那么每个排名都不同，此时无需再排序。

O(n) 做法

在一般的题目中，常数较小的倍增求后缀数组是完全够用的，求后缀数组以外的部分也经常有 的复杂度，倍增求解后缀数组不会成为瓶颈。

但如果遇到特殊题目、时限较紧的题目，或者是你想追求更短的用时，就需要学习 求后缀数组的方法。

SA-IS

可以参考 诱导排序与 SA-IS 算法，另外它的 评论页面 也有参考价值。

DC3

可以参考[2009]后缀数组——处理字符串的有力工具 by. 罗穗骞。

后缀数组的应用

寻找最小的循环移动位置

将字符串 复制一份变成 就转化成了后缀排序问题。

例题：「JSOI2007」字符加密。

在字符串中找子串

任务是在线地在主串 中寻找模式串 。在线的意思是，我们已经预先知道知道主串 ，但是当且仅当询问时才知道模式串 。我们可以先构造出 的后缀数组，然后查找子串 。若子串 在 中出现，它必定是 的一些后缀的前缀。因为我们已经将所有后缀排序了，我们可以通过在 数组中二分 来实现。比较子串 和当前后缀的时间复杂度为 ，因此找子串的时间复杂度为 。注意，如果该子串在 中出现了多次，每次出现都是在 数组中相邻的。因此出现次数可以通过再次二分找到，输出每次出现的位置也很轻松。

从字符串首尾取字符最小化字典序

例题：「USACO07DEC」Best Cow Line。

题意：给你一个字符串，每次从首或尾取一个字符组成字符串，问所有能够组成的字符串中字典序最小的一个。

height 数组

LCP（最长公共前缀）

两个字符串 和 的 LCP 就是最大的 () 使得 。

下文中以 表示后缀 和后缀 的最长公共前缀（的长度）。

height 数组的定义

，即第 名的后缀与它前一名的后缀的最长公共前缀。

可以视作 。

O(n) 求 height 数组需要的一个引理

O(n) 求 height 数组的代码实现

利用上面这个引理暴力求即可：

不会超过 ，最多减 次，所以最多加 次，总复杂度就是 。

height 数组的应用

两子串最长公共前缀

感性理解：如果 一直大于某个数，前这么多位就一直没变过；反之，由于后缀已经排好序了，不可能变了之后变回来。

严格证明可以参考[2004]后缀数组 by. 徐智磊。

有了这个定理，求两子串最长公共前缀就转化为了

RMQ 问题。

比较一个字符串的两个子串的大小关系

假设需要比较的是 和 的大小关系。

若 ，。

否则，。

不同子串的数目

子串就是后缀的前缀，所以可以枚举每个后缀，计算前缀总数，再减掉重复。

“前缀总数”其实就是子串个数，为 。

如果按后缀排序的顺序枚举后缀，每次新增的子串就是除了与上一个后缀的 LCP 剩下的前缀。这些前缀一定是新增的，否则会破坏 的性质。只有这些前缀是新增的，因为 LCP 部分在枚举上一个前缀时计算过了。

所以答案为：

出现至少 k 次的子串的最大长度

例题：「USACO06DEC」Milk Patterns。

是否有某字符串在文本串中至少不重叠地出现了两次

可以二分目标串的长度 ，将 数组划分成若干个连续 LCP 大于等于 的段，利用 RMQ 对每个段求其中出现的数中最大和最小的下标，若这两个下标的距离满足条件，则一定有长度为 的字符串不重叠地出现了两次。

连续的若干个相同子串

我们可以枚举连续串的长度 ，按照 对整个串进行分块，对相邻两块的块首进行 LCP 与 LCS 查询，具体可见[2009]后缀数组——处理字符串的有力工具。

例题：「NOI2016」优秀的拆分。

结合并查集

某些题目求解时要求你将后缀数组划分成若干个连续 LCP 长度大于等于某一值的段，亦即将 数组划分成若干个连续最小值大于等于某一值的段并统计每一段的答案。如果有多次询问，我们可以将询问离线。观察到当给定值单调递减的时候，满足条件的区间个数总是越来越少，而新区间都是两个或多个原区间相连所得，且新区间中不包含在原区间内的部分的 值都为减少到的这个值。我们只需要维护一个并查集，每次合并相邻的两个区间，并维护统计信息即可。

经典题目：「NOI2015」品酒大会

结合线段树

某些题目让你求满足条件的前若干个数，而这些数又在后缀排序中的一个区间内。这时我们可以用归并排序的性质来合并两个结点的信息，利用线段树维护和查询区间答案。

结合单调栈

例题：「AHOI2013」差异

类似的题目：「HAOI2016」找相同字符。

习题

• Uva 760 - DNA Sequencing
• Uva 1223 - Editor
• Codechef - Tandem
• Codechef - Substrings and Repetitions
• Codechef - Entangled Strings
• Codeforces - Martian Strings
• Codeforces - Little Elephant and Strings
• SPOJ - Ada and Terramorphing
• SPOJ - Ada and Substring
• UVA - 1227 - The longest constant gene
• SPOJ - Longest Common Substring
• UVA 11512 - GATTACA
• LA 7502 - Suffixes and Palindromes
• GYM - Por Costel and the Censorship Committee
• UVA 1254 - Top 10
• UVA 12191 - File Recover
• UVA 12206 - Stammering Aliens
• Codechef - Jarvis and LCP
• LA 3943 - Liking's Letter
• UVA 11107 - Life Forms
• UVA 12974 - Exquisite Strings
• UVA 10526 - Intellectual Property
• UVA 12338 - Anti-Rhyme Pairs
• DevSkills Reconstructing Blue Print of Life
• UVA 12191 - File Recover
• SPOJ - Suffix Array
• LA 4513 - Stammering Aliens
• SPOJ - LCS2
• Codeforces - Fake News (hard)
• SPOJ - Longest Commong Substring
• SPOJ - Lexicographical Substring Search
• Codeforces - Forbidden Indices
• Codeforces - Tricky and Clever Password
• LA 6856 - Circle of digits

参考资料

本页面中（4070a9b 引入的部分）主要译自博文 Суффиксный массив 与其英文翻译版 Suffix Array。其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0。

论文：

1. [2004]后缀数组 by. 徐智磊

2. [2009]后缀数组——处理字符串的有力工具 by. 罗穗骞