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