c – 从后缀数组获取LCP的代码如何工作？
|
有人可以解释这个从后缀数组构建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";
}
解决方法
首先,重要的是要认识到算法以原始顺序处理后缀,即它们在输入字符串中出现的顺序.不按字典顺序排列.
因此,如果输入字符串是abxabc,它首先考虑abxabc,然后是bxabc,然后是xabc,依此类推. 对于它按此顺序考虑的每个后缀,它确定后缀的位置,即它的词典前导(*)(所以这里,只有在这里,它使用词典顺序的概念).对于第一个后缀abxabc,词典编辑的前身,即在后缀的词典排序中直接出现在它之前的后缀,是abc.它通过数组C中的O(1)查找来确定这一点,该查找是专门为此目的而准备的. 内循环逐个比较abxabc和abc的字符,并确定这两个后缀共有前2个字符.这是代码中的变量l,这意味着LCP中后缀abxabc的条目必须为2,因此我们设置LCPadj [i] = l.注意,这里我指的是输入字符串中后缀的位置,而不是后缀数组中的位置.所以LCPadj不是LCP阵列(还).这是一个辅助数据结构. 然后它进入下一个字符串,即bxabc.同样,它使用C来查找bc是其词典编辑的前身,然后确定两者共享多少个前缀字符.这就是诀窍：可以肯定的是,这必须至少与前一步骤(即2)相同,减去1.为什么？因为我们当前考虑的字符串bxabc当然是先前考虑的字符串的后缀(abxabc),因此该字符串(abc)的词典编辑前导也必须具有短1个字符(bc)的后缀,并且该后缀也必须在后缀数组中的某个位置,并且它必须与当前考虑的字符串共享其前缀,减去第一个字符.此外,不能有任何其他后缀更短和按字典顺序更接近当前考虑的字符串.如果考虑字典排序的工作方式,后者是合乎逻辑的,但也有正式的证明(例如K?rkk?inen的讲座here中的引理5.10) 这就描述了这里的主要原则.关于完全理解每个变量的作用,您需要注意一些关于代码的注意事项： >如上所述,C是一个辅助数组(长度为n个整数),它为输入字符串中的每个后缀存储另一个后缀的位置,该后缀是其直接的词典前导.这个数组不是从左到右构造的,而是(明智地)从左到右遍历后缀数组,因为这样可以很容易地确定任何字符串的直接词典上的前导：从位置开始的后缀的直接词典编辑前身suffixArr [i]当然必须位于suffixArr [i-1]的位置.在代码中确认这是C的定义方式. 我希望这有帮助.如果没有,请告诉我. (*)字典系列的前身是指字典顺序的后缀列表中后缀的前一个前缀,即后缀数组中其后缀的后缀. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |