suffix-array - 后缀阵列的 LCP 阵列

Question

如何计算后缀数组的 LCP 数组？它不一定是最有效的。O(n log n) 或 O(n) 都可以。如果可能的话，一些相对容易编码的东西。

Answer 1

这是一个简单的 C++ 实现。最长公共前缀（LCP）将保存在 lcp[MAX] 数组中：）

char str[MAX];
int n,gap,sa[MAX],pos[MAX],tmp[MAX],lcp[MAX];
// sa stores the sorted index of the suffixes
// pos stores the serial number of a index in the sorted sequence
bool sufCmp(int i, int j)
{
    if(pos[i]!=pos[j])
      return pos[i]<pos[j];
    i+=gap;
    j+=gap;
    return (i<n&&j<n)?pos[i]<pos[j]:i>j;
}
void buildSA()
{
    n=strlen(str);
    for(int i=0;i<n;i++)
      sa[i]=i,pos[i]=str[i];
    for(gap=1;;gap*=2)
    {
        sort(sa,sa+n,sufCmp);
        for(int i=0;i<n-1;i++)
          tmp[i+1]=tmp[i]+sufCmp(sa[i],sa[i+1]);
        for(int i=0;i<n;i++)
          pos[sa[i]]=tmp[i];
        if(tmp[n-1]==n-1)
          break;
    }
}
void buildLCP()
{
    for(int i=0,k=0;i<n;++i)
    {
        if(pos[i]==n-1)
          lcp[pos[i]]=0;
        else
        {
            for(int j=sa[pos[i]+1];str[i+k]==str[j+k];)
              k++;
            lcp[pos[i]]=k;
            if(k)
              k--;
        }
    }
}