algorithm - 后缀数组DC3算法

Question

我将复习 DC3 算法，这是一种用于构造后缀数组的线性时间算法。我无法理解论文中的技术 found here .

我无法理解论文第 6 页中提到的重命名是如何完成的。如何按照步骤 1 完成重命名。附录中的相关代码部分是:

for (int i = 0; i < n02; i++) 
{
     if (T[SA12[i]] != c0 || T[SA12[i]+1] != c1 || T[SA12[i]+2] != c2)
     { 
          name++; c0 = T[SA12[i]]; c1 = T[SA12[i]+1]; c2 = T[SA12[i]+2]; 
     }
     if (SA12[i] % 3 == 1) 
     { 
          R[SA12[i]/3] = name; 
     } // write to R1
     else
     { 
          R[SA12[i]/3 + n0] = name; 
     } // write to R2
 }

请帮助我理解这部分。 (此代码来自pdf的第20页)

Answer 1

存储库 DC3 Algorithm包含 tutorial document并且可用 C++ 实现。