在计算机科学里, 后缀数组（英语：suffix array）是一个通过对字符串的所有后缀经过排序后得到的数组。此数据结构被运用于全文索引、数据压缩算法、以及生物信息学。
后缀数组介绍
在计算机科学里, 后缀数组（英语：suffix array）是一个通过对字符串的所有后缀经过排序后得到的数组。此数据结构被运用于全文索引、数据压缩算法、以及生物信息学。
后缀数组被乌迪·曼伯尔与尤金·迈尔斯于1990年提出，作为对后缀树的一种替代，更简单以及节省空间。它们也被Gaston Gonnet 于1987年独立发现，并命名为“PAT数组”。
后缀数组简介
在计算机科学里,后缀数组（英语：suffix array）是一个通过对字符串的所有后缀经过排序后得到的数组。此数据结构被运用于全文索引、数据压缩算法、以及生物信息学。
后缀数组被乌迪·曼伯尔与尤金·迈尔斯于1990年提出，作为对后缀树的一种替代，更简单以及节省空间。它们也被Gaston Gonnet 于1987年独立发现，并命名为“PAT数组”。
后缀数组定义
令字符串
， 表示S的子字符串，下标从i到j。S的后缀数组A被定义为一个数组，内容是S的所有后缀经过字典排序后的起始下标。对于所有的有：
。后缀数组例子
考虑字符串S=banana$:
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
b | a | n | a | n | a | $ |
字符串的结尾是特殊字符$，用作特殊标志。该字符串有以下后缀：
后缀 | i |
|---|---|
banana$ | 1 |
anana$ | 2 |
nana$ | 3 |
ana$ | 4 |
na$ | 5 |
a$ | 6 |
$ | 7 |
后缀经过升序排序后：
后缀 | i |
|---|---|
$ | 7 |
a$ | 6 |
ana$ | 4 |
anana$ | 2 |
banana$ | 1 |
na$ | 5 |
nana$ | 3 |
后缀数组A包含这些后缀的起始位置：
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
A | 7 | 6 | 4 | 2 | 1 | 5 | 3 |
