概述
这是一个用于后缀数组构造的 O(n log n) 算法（或者更确切地说，如果使用::sort了 2 次桶排序而不是）。
它首先对原始字符串的 2-gram (*)进行排序，然后是 4-gram，然后是 8-gram，依此类推，S因此在第 i 次迭代中，我们对 2 i- gram 进行排序。显然，这样的迭代不会超过 log 2 (n)，诀窍是通过确保两个 2 i -gram 的每次比较在O (1) 时间（而不是 O(2 i ) 时间）。
它是如何做到的？好吧，在第一次迭代中，它对 2-gram（又名二元组）进行排序，然后执行所谓的字典重命名。这意味着它创建了一个新数组（长度为n），为每个二元组存储其在二元组排序中的排名。
字典重命名的示例：假设我们有一些 bigrams的排序{'ab','ab','ca','cd','cd','ea'}列表。然后，我们通过从左到右分配等级（即字典名称），从等级 0 开始，并在遇到新的二元组变化时增加等级。所以我们分配的排名如下：
ab : 0
ab : 0 [no change to previous]
ca : 1 [increment because different from previous]
cd : 2 [increment because different from previous]
cd : 2 [no change to previous]
ea : 3 [increment because different from previous]
这些等级被称为词典名称。
现在，在下一次迭代中，我们对 4-gram 进行排序。这涉及到不同 4-gram 之间的大量比较。我们如何比较两个 4-gram？好吧，我们可以逐个字符地比较它们。每次比较最多需要 4 次操作。但是，我们使用前面步骤中生成的等级表，通过查找其中包含的两个二元组的等级来比较它们。该排名表示前一个 2-gram 排序的词典排名，因此，如果对于任何给定的 4-gram，其第一个 2-gram 的排名高于另一个 4-gram 的第一个 2-gram，那么它必须在词典上更大在前两个字符的某处。因此，如果对于两个 4-gram，第一个 2-gram 的秩相同，则它们在前两个字符。换句话说，秩表中的两次查找足以比较两个 4-gram 的所有 4 个字符。
排序后，我们再次创建新的词典名称，这次是 4-gram。
在第三次迭代中，我们需要按 8-gram 排序。同样，在上一步的字典排序表中进行两次查找就足以比较两个给定 8-gram 的所有 8 个字符。
等等。每次迭代i有两个步骤：
按 2 i -gram 排序，使用上一次迭代中的字典名称，以便在 2 个步骤（即 O(1) 时间）中进行比较
创建新的词典名称
我们重复此操作，直到所有 2 个i -gram 都不同。如果发生这种情况，我们就完成了。我们怎么知道是否一切都不一样？好吧，词典名称是一个递增的整数序列，从 0 开始。因此，如果在迭代中生成的最高词典名称与 相同n-1，那么每个 2 i -gram 必须已被赋予其自己的不同词典名称。
执行
现在让我们看一下确认所有这些的代码。使用的变量如下：sa[]是我们正在构建的后缀数组。pos[]是秩查找表（即它包含词典名称），具体而言，pos[k]包含k上一步的第-th m-gram 的词典名称。tmp[]是用于帮助创建的辅助数组pos[]。
我将在代码行之间给出进一步的解释：
void buildSA()
{
N = strlen(S);
/* This is a loop that initializes sa[] and pos[].
For sa[] we assume the order the suffixes have
in the given string. For pos[] we set the lexicographic
rank of each 1-gram using the characters themselves.
That makes sense, right? */
REP(i, N) sa[i] = i, pos[i] = S[i];
/* Gap is the length of the m-gram in each step, divided by 2.
We start with 2-grams, so gap is 1 initially. It then increases
to 2, 4, 8 and so on. */
for (gap = 1;; gap *= 2)
{
/* We sort by (gap*2)-grams: */
sort(sa, sa + N, sufCmp);
/* We compute the lexicographic rank of each m-gram
that we have sorted above. Notice how the rank is computed
by comparing each n-gram at position i with its
neighbor at i+1. If they are identical, the comparison
yields 0, so the rank does not increase. Otherwise the
comparison yields 1, so the rank increases by 1. */
REP(i, N - 1) tmp[i + 1] = tmp[i] + sufCmp(sa[i], sa[i + 1]);
/* tmp contains the rank by position. Now we map this
into pos, so that in the next step we can look it
up per m-gram, rather than by position. */
REP(i, N) pos[sa[i]] = tmp[i];
/* If the largest lexicographic name generated is
n-1, we are finished, because this means all
m-grams must have been different. */
if (tmp[N - 1] == N - 1) break;
}
}
关于比较功能
该函数sufCmp用于按字典顺序比较两个 (2*gap)-gram。所以在第一次迭代中它比较二元组，在第二次迭代中比较 4-gram，然后是 8-gram，依此类推。这由 控制gap，它是一个全局变量。
一个天真的实现sufCmp是这样的：
bool sufCmp(int i, int j)
{
int pos_i = sa[i];
int pos_j = sa[j];
int end_i = pos_i + 2*gap;
int end_j = pos_j + 2*gap;
if (end_i > N)
end_i = N;
if (end_j > N)
end_j = N;
while (i < end_i && j < end_j)
{
if (S[pos_i] != S[pos_j])
return S[pos_i] < S[pos_j];
pos_i += 1;
pos_j += 1;
}
return (pos_i < N && pos_j < N) ? S[pos_i] < S[pos_j] : pos_i > pos_j;
}
这将比较第 i 个后缀开头的 (2*gap)-gram 和第pos_i:=sa[i]j 个后缀开头的那个pos_j:=sa[j]。它会逐个字符地比较它们，即与 比较S[pos_i]，S[pos_j]然后S[pos_i+1]与S[pos_j+1]等等。只要字符相同，它就会继续。一旦它们不同，如果第 i 个后缀中的字符小于第 j 个后缀中的字符，则返回 1，否则返回 0。（请注意，return a<b在函数中返回int意味着如果条件为真则返回 1，如果条件为假则返回 0。）
return-statement 中复杂的外观条件处理 (2*gap)-grams 之一位于字符串末尾的情况。在这种情况下，pos_i或者pos_j将N在所有 (2*gap) 字符被比较之前到达，即使直到该点的所有字符都是相同的。如果第 i 个后缀在末尾，它将返回 1，如果第 j 个后缀在末尾，则返回 0。这是正确的，因为如果所有字符都相同，则较短的字符在字典上更小。如果pos_i已到达末尾，则第 i 个后缀必须比第 j 个后缀短。
显然，这种简单的实现是 O(gap)，即它的复杂性在 (2*gap)-gram 的长度上是线性的。但是，您的代码中使用的函数使用字典名称将其降低到 O(1)（具体来说，最多降低到两次比较）：
bool sufCmp(int i, int j)
{
if (pos[i] != pos[j])
return pos[i] < pos[j];
i += gap;
j += gap;
return (i < N && j < N) ? pos[i] < pos[j] : i > j;
}
如您所见，我们不是查找单个字符S[i]和S[j]，而是检查第 i 个和第 j 个后缀的字典顺序。字典等级是在之前的迭代中为间隙图计算的。因此，如果pos[i] < pos[j]，那么第 i 个后缀sa[i]必须以一个 gap-gram 开头，该 gap-gram 在字典上小于 开头的 gap-gram sa[j]。换句话说，简单地通过查找pos[i]和pos[j]比较它们，我们已经比较了两个后缀的第一个间隙字符。
如果排名相同，我们继续与pos[i+gap]比较pos[j+gap]。这与比较 (2*gap)-grams 的下一个间隙字符相同，即后半部分。如果秩再次相同，则两个 (2*gap)-gram 相同，因此我们返回 0。否则，如果第 i 个后缀小于第 j 个后缀，则返回 1，否则返回 0。
例子
下面的例子说明了算法是如何运行的，并且特别展示了字典名称在排序算法中的作用。
我们要排序的字符串是abcxabcd. 为此生成后缀数组需要 3 次迭代。在每次迭代中，我将显示S（字符串）、sa（后缀数组的当前状态）和tmpand pos，它们表示字典名称。
首先，我们初始化：
S abcxabcd
sa 01234567
pos abcxabcd
请注意，最初表示一元组的字典顺序的字典名称如何与字符（即一元组）本身完全相同。
第一次迭代：
排序sa，使用二元组作为排序标准：
sa 04156273
前两个后缀是 0 和 4，因为它们是二元组 'ab' 的位置。然后是 1 和 5（bigram 'bc' 的位置），然后是 6（bigram 'cd'），然后是 2（bigram 'cx'）。然后是 7（不完整的二元组 'd'），然后是 3（二元组'xa'）。显然，位置对应于顺序，仅基于字符二元组。
生成词典名称：
tmp 00112345
如上所述，词典名称被分配为递增的整数。前两个后缀（都以 bigram 'ab' 开头）得到 0，接下来的两个（都以 bigram 'bc' 开头）得到 1，然后是 2、3、4、5（每个都是不同的 bigram）。
最后，我们根据 , 中的位置进行映射sa，得到pos：
sa 04156273
tmp 00112345
pos 01350124
（pos生成的方式是这样的：sa从左到右遍历，并使用条目来定义索引。使用对应的条目pos来定义该索引的tmp值。所以，，，，，，等等。索引来自，值来自。）pos[0]:=0pos[4]:=0pos[1]:=1pos[5]:=1pos[6]:=2satmp
第二次迭代：
我们再次排序sa，并再次查看来自的二元组pos（每个表示原始字符串的两个二元组的序列）。
sa 04516273
注意 1 5 的位置与之前版本的sa. 以前是 15，现在是 51。这是因为在上一次迭代中，atpos[1]的二元组和 at 的二元组pos[5]曾经是相同的（两者bc），但现在 at 的二元组pos[5]是12，而 at 的二元组pos[1]是13。所以 position5在position之前1。这是因为字典名称现在每个都代表原始字符串的二元组：pos[5]代表bc和pos[6]代表“cd”。所以，它们一起代表bcd，而pos[1]代表bc和pos[2]代表cx，所以它们一起代表bcx, 这在字典上确实大于bcd.
sa同样，我们通过从左到右筛选当前版本并比较相应的二元组来生成词典名称pos：
tmp 00123456
前两个条目仍然相同（均为 0），因为对应的二元组pos都是01. 其余的是严格递增的整数序列，因为其中的所有其他二元组pos都是唯一的。
我们像以前一样执行到新的映射pos（从 获取索引sa和从 获取值tmp）：
sa 04516273
tmp 00123456
pos 02460135
第三次迭代：
我们再次排序sa，采用pos（一如既往）的二元组，现在每个表示原始字符串的 4 个二元组的序列。
sa 40516273
您会注意到现在前两个条目已经交换了位置：04已变为40. 这是因为二元组 at pos[0]is02而一个 at pos[4]is 01，后者显然在字典上更小。深层原因是这两个分别代表abcx和abcd。
生成字典名称会产生：
tmp 01234567
它们都是不同的，即最高的是7，也就是n-1。所以，我们完成了，因为现在排序是基于完全不同的 m-gram。即使我们继续，排序顺序也不会改变。
改进建议
用于在每次迭代中对 2 i -gram 进行排序的算法似乎是内置的sort（或std::sort）。这意味着它是一种比较排序，在最坏的情况下，每次迭代都需要 O(n log n) 时间。由于在最坏的情况下有 log n 次迭代，这使其成为 O(n (log n) 2 ) 时间的算法。然而，排序可以通过使用两次桶排序来执行，因为我们用于排序比较的键（即上一步的词典名称）形成一个递增的整数序列。因此，这可以改进为用于后缀排序的实际 O(n log n) 时间算法。
评论
我相信这是 Manber 和 Myers 在 1992 年的论文中建议的后缀数组构造的原始算法（Google Scholar 上的链接；它应该是第一个热门，并且可能有指向 PDF 的链接）。这（同时，但独立于 Gonnet 和 Baeza-Yates 的一篇论文）是引入后缀数组（当时也称为 pat 数组）作为值得进一步研究的数据结构的原因。
后缀数组构造的现代算法是 O(n)，因此上述算法不再是可用的最佳算法（至少在理论上，最坏情况复杂度方面不是）。
脚注
(*) 2-gram是指原始字符串的两个连续字符的序列。例如，whenS=abcde是字符串，那么ab,bc,cd,de是 的 2-gramS。同样，abcd和bcde是 4 克。通常，m-gram（对于正整数 m）是一系列m连续字符。1-gram 也称为 unigram，2-gram 称为 bigram，3-gram 称为 trigram。有些人继续使用四角星、五角星等。
请注意，Sstarts 和 position的后缀i是 的 (ni)-gram S。此外，每个 m-gram（对于任何 m）都是 的后缀之一的前缀S。因此，对 m-gram 进行排序（对于 m 尽可能大）可能是排序后缀的第一步。