string - 了解 DC3/Skew 算法的实现以创建后缀数组线性时间

Question

我正在尝试了解 Karkkainen, P. Sanders 对线性时间后缀数组创建算法的实现。算法详情可见here .

我设法理解了整体概念，但未能将其与提供的实现相匹配，因此无法清楚地掌握它。

这是让我感到困惑的初始代码路径。

根据论文:n0、n1、n2 表示从 i mod 3 = (0,1,2) 开始的三元组数

根据代码:n0 = (n + 2)/3，n1 = (n + 1)/3，n2 = n/3； => 这些初始化是如何导出的？

根据论文:我们需要创建 T`，它是 i mod 3 != 0 处的三元组串联

根据代码:n02 = n0 + n2； s12 = [n02] ==> n02 怎么来的？它应该是 n12 即 n1 + n2。

根据代码:for (int i = 0, j = 0; i < n + (n0 - n1); i++) 用三元组填充 s12 使得 i%3 != 0; => 为什么 for 循环运行 n + (n0 - n1) 次？它应该只是 n1 + n2。不应该？

由于这些，我无法继续进行 :( 请提供帮助。

Answer 1

考虑以下示例，其中输入的长度为 n=13:

 STA | CKO | WER | FLO | W

As per code : n0 = (n + 2) / 3, n1 = (n + 1) / 3, n2 = n / 3; => How these initialisations has been derived?

请注意，如果 n mod3 = 0，则 i mod3 = 0 的三元组数为 n/3，否则为 n/3+1(如果 n mod3 = 1 或 n mod3 = 2)。在当前示例中，n/3 = 4，但由于最后一个三元组“W”不完整，因此不计入整数除法。直接进行此计算的“技巧”是使用 (n+2)/3。实际上，如果 n mod3 = 0，则整数除法 (n+2)/3 和 n/3 的结果将相同。但是，如果 n mod3 = 1 或 2，则 (n+2)/3 的结果将为 n/3+1。 n1、n2也一样。

As per code : n02 = n0 + n2; s12 = [n02] ==> How came n02? It should be n12 i.e n1 + n2. As per code : for (int i = 0, j = 0; i < n + (n0 - n1); i++) fill s12 with triplets such that i%3 != 0; => Why for loop runs for n + (n0 - n1) times ? It should be simply n1 + n2. Should't be ?

两个问题的答案相同。在我们的例子中，我们有一个像这样的 B12 缓冲区:

B12 = B1 U B2 = {TA KO ER LO}

所以您首先对后缀进行排序，最后得到一个 B12 的后缀数组，它有 8 个元素。要进行合并步骤，我们首先需要计算 B0 的后缀数组，它是通过对元组 (B0(i),rank(i+1)) 进行排序而获得的...但是最后一个三元组具有的具体情况只有一个元素(W)有问题，因为没有为 B0 的最后一个元素定义 rank(i+1):

B0 = {0,3,6,9,12}

按字母顺序排序的结果是

SA0 = {3, 9, 0, ?, ?}

由于索引 6 和 12 包含一个 'W'，按字母顺序排序是不够的，我们需要检查哪个在排名表中排在第一位，所以让我们检查它们后缀的排名.. 哦，等等! rank(13) 未定义!

这就是为什么当最后一个三元组仅包含一个元素时(如果 n mod3 = 0)，我们将虚拟 0 添加到输入的最后一个三元组。因此，无论 n1 的大小如何，B12 的大小都是 n0+n2，如果 B0 大于 B1(在这种情况下 n0-n1 = 1)，则需要向 B12 添加一个额外的元素。

希望一切都清楚。