접미어 배열 용 LCP 배열

Question

접미어 배열에 대해 LCP 배열을 계산하는 방법은 무엇입니까? 가장 효율적 일 필요는 없습니다. O (n log n) 또는 O (n)이 수행합니다. 가능한 경우 코드 작성이 비교적 쉽습니다.

Answer 1

다음은 간단한 C++ 구현입니다. LCP (Longest Common Prefix)는 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--; 
     } 
    } 
}