定义

后缀数组：后缀数组SA是一个一维数组，它保存1..n的某个排列SA[1]，SA[2]，……，SA[n]，并且保证 Suffix(SA[i])<Suffix(SA[i+1])。每个数组中存储的值为字典序为i的原字符串后缀在原串中的位置。