从后缀数组获取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.它通过数组中的O(1)查找来确定这一点,该查找C是专门为此目的而准备的.

内循环逐个比较字符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 )

这就描述了这里的主要原则.关于完全理解每个变量的作用,您需要注意一些关于代码的注意事项:

• 如上所述,C是一个辅助数组(n长度为整数),它为输入字符串中的每个后缀存储另一个后缀的位置,该后缀是其直接的词典前导.这个数组不是从左到右构造的,而是(明智地)从左到右遍历后缀数组,因为这样可以很容易地确定任何字符串的直接词典上的前导:从位置开始的后缀的直接词典编辑前身suffixArr[i]当然必须位于位置suffixArr[i-1].在代码中确认这是如何C定义的.
• 如上所述,LCPadj按照它们在输入字符串中出现的顺序存储后缀的LCP值,而不是它们在后缀数组中出现的顺序.这就是为什么在输出时,LCPadj不是从左到右打印,而是从左到右遍历后缀数组,然后LCPadj[i]按顺序打印.确认是这种情况.

我希望这有帮助.如果没有,请告诉我.

^(*)通过辞书前辈我的意思是直接在后缀的字典顺序列表后缀的前身,即后缀为它的左边紧邻的后缀数组英寸