相关疑难解决方法(0)

在过去的几周里,我试图弄清楚如何在另一个字符串中有效地找到字符串模式.

我发现很长一段时间,最有效的方法是使用后缀树.但是,由于这种数据结构在空间上非常昂贵,我进一步研究了后缀数组的使用(使用的空间要少得多).不同的论文,如"后缀数组:一种新的在线字符串搜索方法"(Manber&Myers,1993)指出,搜索子字符串可以在O(P + log(N))中实现(其中P是通过使用二进制搜索和后缀数组以及LCP数组,模式的长度和N是字符串的长度.

我特别研究了后一篇论文来理解搜索算法.这个答案在帮助我理解算法方面做得非常出色(并顺便将其纳入LCP维基百科页面).

但我仍在寻找实现此算法的方法.特别是所提到的LCP-LR阵列的构造看起来非常复杂.

参考文献:

Manber&Myers,1993:Manber,Udi; Myers,Gene,SIAM Journal on Computing,1993,Vol.22(5),pp.935-948,http: //epubs.siam.org/doi/pdf/10.1137/0222058

更新1

只是为了强调我感兴趣的东西:我理解LCP数组,并找到了实现它们的方法.但是,"普通"LCP阵列不适合有效的模式匹配(如参考文献中所述).因此,我对实现LCP-LR阵列感兴趣,这似乎比实现LCP阵列复杂得多

更新2

添加了参考文件的链接

我一直在学习后缀数组的创建,我明白我们首先按照第一个字符对所有后缀进行排序,然后根据前2个字符,然后是前4个字符,依此类推,同时要考虑的字符数小于2n.

但我怀疑的是为什么我们不选择前3个字符,然后是9 ......等等.为什么只考虑2个字符,因为字符串是相同字符串的一部分而不是不同的随机字符串？

有人可以解释这个从后缀数组构建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";


}