SA-IS 是一种巧妙手法，可以在线性时空复杂度内求出一个字符串 S 的后缀数组 SA。

先定义一些东西：

• Suf_i 指 S_{i...n}，意即从第 i 个字符开始的后缀。
• SA_i 指对 Suf 内的 n 个字符串做字典序递增排列后的第 i 个串在原串中第一个字符的下标（从 1 开始），也就是“后缀数组”。
• Rank_i 指对 Suf 内的 n 个字符串做字典序排列后 Suf_i 的下标（从 1 开始），也叫“排名数组”。
• 我们称一个后缀 Suf_i(1<=i<=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 的类型。