SA-IS 是一种巧妙手法，可以在线性时空复杂度内求出一个字符串 $S$ 的后缀数组 SA。 先定义一些东西： - $Suf_i$ 指 $S_{i\dots n}$，意即从第 $i$ 个字符开始的后缀。 - $SA_i$ 指对 $Suf$ 内的 $n$ 个字符串做字典序递增排列后的第 $i$ 个串在原串中第一个字符的下标（从 $1$ 开始），也就是“后缀数组”。 - $Rank_i$ 指对 $Suf$ 内的 $n$ 个字符串做字典序排列后 $Suf_i$ 的下标（从 $1$ 开始），也叫“排名数组”。 - 我们称一个后缀 $Suf_i(1\le i\le n)$ 是 L(for "larger")-type 的，当且仅当 $SA_i>SA_{i+1}$。若一个后缀不是 L-type 的，则我们称它是 S(for "smaller")-type 的。我们定义 $Suf_n$ 是 L-type 的，$Suf_{n+1}$ 是 S-type 的（可以方便地理解成在字符串后添加一个不在 $\Sigma$ 中的特殊/哨兵字符 `*`，它的字典序比 $\Sigma$ 中的任何字符都大）。为了简要书写，定义 $Type_i$ 为 $Suf_i$ 的**类型**。