最長共同前綴屬性

Question

我正在通過後綴數組及其用於計算兩個後綴的最長共同前綴。

源說：

「兩個後綴之間的LCP是在陣列上的最小所有對它們之間的相鄰的後綴的LCP的的」

即lcp(x,y)=min{ lcp(x,x+1),lcp(x+1,x+2),.....,lcp(y-1,y) } 其中x和y是字符串的兩個後綴從哪裏開始的字符串的兩個索引。

我不相信與字符串"abca"的示例中的說法。

lcp(1,4)=1（考慮1個基於索引）

，但如果我套用上述公式然後

lcp(1,4)=min{lcp(1,2),lcp(2,3),lcp(3,4)}

，我認爲lcp(1,2)=0。根據公式，答案必須是0。

我在某處錯了嗎？

Answer 1

我認爲源引用的索引不是字符串本身的索引，而是排序後綴的索引。

a 
abca 
bca 
ca 

因此

lcp(1,2) = lcp(a, abca) = 1 
lcp(1,4) = min(lcp(1,2), lcp(2,3), lcp(3,4)) = 0 

Answer 2

你不能簡單地計算最小所有對陣列上它們之間的相鄰後綴的LCP年代發現任何兩個後綴的LCP。

我們可以用下面的幫助計算任何後綴的液晶聚合物（I，J） ：

LCP(suffix i,suffix j)=LCP[RMQ(i + 1; j)] 

也注意到(i<j)爲LCP (suff i,suff j)可能不等於necessarly LCP (Suff j,suff i)。 RMQ是範圍最小查詢量。

此paper的第3頁。

Details: 

步驟1： 首先計算鄰道/連續後綴對的LCP。

n =字符串的長度。

suffixArray []是後綴數組。

void calculateadjacentsuffixes(int n) 
{ 
    for (int i=0; i<n; ++i) Rank[suffixArray[i]] = i; 
    Height[0] = 0; 
    for (int i=0, h=0; i<n; ++i) 
    { 
     if (Rank[i] > 0) 
     { 
      int j = suffixArray[Rank[i]-1]; 
      while (i + h < n && j + h < n && str[i+h] == str[j+h]) 
      { 
       h++; 
      } 
      Height[Rank[i]] = h; 
      if (h > 0) h--; 
     } 
    } 
} 

注意：高度[I]（下標i-1，標i）即= LCP材料。高度數組包含相鄰後綴的LCP。

步驟2：

計算使用RMQ概念任何兩個標i，j的LCP。 RMQ預先計算功能：

void preprocesses(int N) 
{ 
    int i, j; 

    //initialize M for the intervals with length 1 
    for (i = 0; i < N; i++) 
     M[i][0] = i; 

    //compute values from smaller to bigger intervals 
    for (j = 1; 1 << j <= N; j++) 
    { 
     for (i = 0; i + (1 << j) - 1 < N; i++) 
     { 
      if (Height[M[i][j - 1]] < Height[M[i + (1 << (j - 1))][j - 1]]) 
      { 
       M[i][j] = M[i][j - 1]; 
      } 
      else 
      { 
       M[i][j] = M[i + (1 << (j - 1))][j - 1]; 
      } 
     } 
    } 
} 

步驟3：計算任意兩個標i之間LCP，J

int LCP(int i,int j) 
{ 
    /*Make sure we send i<j always */ 
    /* By doing this ,it resolve following 
    suppose ,we send LCP(5,4) then it converts it to LCP(4,5) 
    */ 
    if(i>j) 
     swap(i,j); 

    /*conformation over*/ 

    if(i==j) 
    { 
     return (Length_of_str-suffixArray[i]); 
    } 
    else 
    { 
     return Height[RMQ(i+1,j)]; 
     //LCP(suffix i,suffix j)=LCPadj[RMQ(i + 1; j)] 
     //LCPadj=LCP of adjacent suffix =Height. 
    } 
} 

哪裏RMQ函數是：

int RMQ(int i,int j) 
{ 
    int k=log((double)(j-i+1))/log((double)2); 
    int vv= j-(1<<k)+1 ; 
    if(Height[M[i][k]]<=Height[ M[vv][ k] ]) 
     return M[i][k]; 
    else 
     return M[ vv ][ k]; 
} 

參見Topcoder tutorials爲RMQ。

您可以通過我的blog查看C++的完整實現。