用於後綴數組的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--; 
     } 
    } 
}