suffix-array - 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--;
        }
    }
}