我也在阅读来自 codechef 和 stackoverflow 的后缀数组构造教程。我能理解的一点是他们说..
它的工作原理是首先对原始字符串 S 的 2-grams(*)、4-grams、8-grams 等进行排序，所以在第 i 次迭代中，我们对 2i-grams 进行排序
等等。每次迭代 i 有两个步骤：
按 2i-gram 排序，使用上一次迭代中的词典名称，以便在 2 个步骤（即 O(1) 时间）中进行比较
创建新的词典名称
我的疑问是：如何使用以 2 克计算的索引为 4 克。?
假设我的 2 个后缀是“ab”、“ac”，那么您如何在 O(1) 时间内进行比较并为它们提供索引。
我真的试过但卡在那里。请提供一些例子，这会有所帮助。提前致谢
假设所有具有长度的子字符串2^k都已排序，现在我们要对所有具有长度的子字符串进行排序2^(k + 1)。这里的关键观察是任何具有长度2^(k + 1)的子字符串都是两个具有长度的子字符串的串联2^k。
例如，在字符串中abacaba，子字符串caba是ca和的串联ba。
但是所有具有长度的子字符串2^k都是排序的，所以我们可以假设它们中的每一个都被分配一个范围内的整数[0 ... n - 1]（我称之为类）基于它在所有具有这个长度的子字符串的排序数组中的位置（相等的字符串应该被分配相等数字，当然，这个数组没有明确维护）。在这种情况下，每个子字符串的长度2^(k + 1)可以表示为一对两个数字(p1, p2)- 分别是第一个和第二个子字符串的类。所以我们需要做的就是从 range 中对一个整数对数组进行排序[0 ... n - 1]。可以使用基数排序在线性时间内完成。2^(k + 1)对这些对进行排序后，我们可以在排序后的数组中使用单次遍历找到所有具有长度的子字符串的类。