c++ - 这个从后缀数组获取 LCP 的代码是如何工作的？

Question

有人能解释一下从后缀数组构造 LCP 的代码是如何工作的吗？ suffixArr[]是一个数组，使得 suffixArr[i]保存字符串中具有等级 i 的后缀的索引值。

 void LCPconstruct()
{
    int i,C[1001],l;
    C[suffixArr[0]] = n;


    for(i=1;i<n;i++)
    C[suffixArr[i]] = suffixArr[i-1];

    l = 0;

   for(i=0;i<n;i++)
   {
    if(C[i]==n)
        LCPadj[i] = 0;
    else
    {
        while(i+l<n && C[i]+l<n && s[i+l] == s[C[i]+l])
            l++;
        LCPadj[i] = l;

        l = max(l-1,0);
    }
  }

  for(i=0;i<n;i++)
     cout<<LCPadj[suffixArr[i]]<<"\n";


}

Answer 1

首先，重要的是要意识到算法按原始顺序处理后缀，即它们在输入字符串中出现的顺序。不按字典顺序排列。

所以如果输入字符串是 abxabc ，它首先考虑 abxabc ，然后 bxabc ，然后 xabc等等。

对于它按此顺序考虑的每个后缀，它确定作为其词典前驱 (*) 的后缀的位置(因此，在这里，并且仅在此处，它使用词典顺序的概念)。对于第一个后缀 abxabc ，字典序的前身，即在后缀的字典序中直接出现在它之前的后缀是 abc .它通过在数组 C 中的 O(1) 查找来确定这一点。 ，这是专门为此目的准备的。

内循环比较abxabc的字符和 abc一一确定这两个后缀的前2个字符是相同的。这是变量 l在您的代码中，这意味着 LCP 中后缀 abxabc 的条目必须是 2，所以我们设置 LCPadj[i] = l .请注意 i这里指的是后缀在输入字符串中的位置，而不是它在后缀数组中的位置。所以LCPadj不是 LCP 阵列(还)。它是一种辅助数据结构。

然后它继续下一个字符串，即 bxabc .它再次使用 C找到bc是其字典序的前身，然后确定两者共享多少前缀字符。诀窍来了:可以肯定，这必须至少与上一步中的一样多(即 2)，减去 1。为什么？因为我们目前考虑的字符串，bxabc , 当然是之前考虑的字符串 ( abxabc ) 的后缀，因此该字符串的字典前身 ( abc ) 也必须有一个短 1 个字符的后缀 ( bc )，并且该后缀也必须位于后缀数组中的某个位置，并且它必须与当前考虑的字符串共享其前缀，减去第一个字符。此外，不可能有任何其他后缀既更短又在字典上更接近当前考虑的字符串。如果您考虑字典排序的工作原理，后者是非常合乎逻辑的，但也有正式的证明(例如 Kärkkäinen 讲座中的引理 5.10 here)

所以这描述了这里工作的主要原则。为了充分理解每个变量的作用，您的代码有几点需要注意:

正如所解释的，C是一个辅助数组(长度为 n 整数)，它为输入字符串中的每个后缀存储其他后缀的位置，该后缀是其直接的字典序前辈。这个数组不是从左到右构造的，而是(明智地)通过从左到右遍历后缀数组，因为这样可以很容易地确定任何字符串的直接字典序前身:从位置开始的后缀的直接字典序前身suffixArr[i]当然必须位于位置 suffixArr[i-1] .在您的代码中确认这是如何C被定义为。

如上所述，LCPadj以它们在输入字符串中出现的顺序存储后缀的 LCP 值，而不是它们在后缀数组中出现的顺序。这就是为什么在输出时，LCPadj不是从左到右打印，而是通过从左到右遍历后缀数组，并打印LCPadj[i]以该顺序。确认是这种情况。

我希望这有帮助。如果没有，请告诉我。

(*) 按字典序排列的前身是指按字典序排列的后缀列表中后缀的直接前身，即后缀数组中紧邻其左侧的后缀。