查看“︁后缀数组”︁的源代码

{{noteTA
|G1=IT
}}
{{Infobox
| above =  后缀数组
| label1 = 类型
| data1 = [[数组]]
| label2 = 发明者
| data2 = {{harvtxt|Manber|Myers|1990}}
| header3 = [[时间复杂度]]([[大O符号]])
| headerstyle = background:lavender
| data4 = 
{{aligned table|cols=3|row1header=y|col1header=y|fullwidth=y
| | 平均 | 最坏情况
<!-- -->
| 空间
| <math>\mathcal{O}(n)</math>
| <math>\mathcal{O}(n)</math>
<!-- -->
| 构建
| <math>\mathcal{O}(n)</math>
| <math>\mathcal{O}(n)</math>
}}
}}

在[[计算机科学]]里, '''后缀数组'''（英語：suffix array）是一个通过对[[字符串]]的所有后缀经过排序后得到的数组。此数据结构被运用于全文索引、数据压缩算法、以及[[生物信息学]]。

后缀数组被{{link-en|烏迪·曼伯爾|Udi Manber}}與{{link-en|尤金·邁爾斯|Eugene Myers}}于1990年提出，作为对[[后缀树]]的一种替代，更简单以及节省空间。它们也被Gaston Gonnet 于1987年獨立发現，并命名为「PAT数组」。

在2016年，[http://arxiv.org/abs/1610.08305 李志泽，李建和霍红卫]{{Wayback|url=http://arxiv.org/abs/1610.08305 |date=20190827083129 }}提出了第一个时间复杂度（线性时间）和空间复杂度（常数空间）都是最优的后缀数组构造算法，解决了该领域长达10年的open problem。

== 定义 ==
令字符串<math>S=S[1]S[2]...S[n]</math>， <math>S[i,j]</math>表示<math>S</math>的子字符串，下标从<math>i</math>到<math>j</math>。

<math>S</math>的后缀数组<math>A</math>被定义为一个数组，内容是<math>S</math>的所有后缀经过字典排序后的起始下标。

对于所有的有：<math>1 < i \leq n</math>: <math>S[A[i-1],n] < S[A[i],n]</math>。


== 例子 ==
考虑字符串 <math>S</math>=<code>banana$</code>:
{| class="wikitable"
|-
!  align="left" | i
| 1 || 2 || 3 || 4 || 5 || 6 || 7
|-
! align="left" | <math>S[i]</math>
| b || a || n || a || n || a || $
|}

字符串的结尾是特殊字符<code>$</code>，用作特殊标志。该字符串有以下后缀：

{|   class="wikitable"
!  align="left" | 后缀 !!  align="left" | i
|-  class="odd"
|  align="left" | banana$ ||  align="left" | 1
|-  class="even"
|  align="left" | anana$ ||  align="left" | 2
|-  class="odd"
|  align="left" | nana$ ||  align="left" | 3
|-  class="even"
|  align="left" | ana$ ||  align="left" | 4
|-  class="odd"
|  align="left" | na$ ||  align="left" | 5
|-  class="even"
|  align="left" | a$ ||  align="left" | 6
|-  class="odd"
|  align="left" | $ ||  align="left" | 7
|}

后缀经过升序排序后：

{|   class="wikitable"
!  align="left" | 后缀 !!  align="left" | i
|-  class="odd"
|  align="left" | $ ||  align="left" | 7
|-  class="even"
|  align="left" | a$ ||  align="left" | 6
|-  class="odd"
|  align="left" | ana$ ||  align="left" | 4
|-  class="even"
|  align="left" | anana$ ||  align="left" | 2
|-  class="odd"
|  align="left" | banana$ ||  align="left" | 1
|-  class="even"
|  align="left" | na$ ||  align="left" | 5
|-  class="odd"
|  align="left" | nana$ ||  align="left" | 3
|}

后缀数组 <math>A</math> 包含这些后缀的起始位置：

{| class="wikitable"
! align="left" | i
| 1 || 2 || 3 || 4 || 5 || 6 || 7
|-
! align="left" | <math>A[i]</math>
| 7 || 6 || 4 || 2 || 1 || 5 || 3
|}

== 外部链接 ==
* [http://algs4.cs.princeton.edu/63suffix/SuffixArray.java.html Java实现的后缀数组]{{Wayback|url=http://algs4.cs.princeton.edu/63suffix/SuffixArray.java.html |date=20131212033504 }}

{{字符串}}

[[Category:数组]]
[[Category:子字符串索引]]
[[Category:字符串数据结构]]