3

我试图了解 Karkkainen，P. Sanders 的线性时间后缀数组创建算法的实现。可以在此处找到算法的详细信息。

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

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

根据论文：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。不应该吗？

由于这些原因，我无法继续:(请帮忙。

4

1 回答 1

2

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

 STA | CKO | WER | FLO | W

根据代码：n0 = (n + 2) / 3, n1 = (n + 1) / 3, n2 = n / 3; => 这些初始化是如何得出的？

请注意，如果 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。

根据代码：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。不应该吗？

两个问题都有相同的答案。在我们的示例中，我们将有一个像这样的 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。那么 B12 的大小是 n0+n2，不管 n1 的大小，如果 B0 大于 B1（在这种情况下 n0-n1 = 1），则需要在 B12 中添加一个额外的元素。

希望很清楚。

于 2014-11-17T11:23:48.370 回答