CODEWITHSUNDEEP
suffix-arraystring-algorithmlongest-prefix
user3415207
user3415207

Reputation: 11

LCP array for Suffix Array

How to compute the LCP array for a suffix array? It doesn't have to be the most efficient. O(n log n) or O(n) will do. Something relatively easy to code if possible.

Upvotes: 1

Views: 323

Answers (1)

Ali Akber
Ali Akber

Reputation: 3800

Here is a simple C++ implementation. Longest common prefix(LCP) will be saved in lcp[MAX] array :)

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

Upvotes: 3

Related Questions