最长共同前缀属性

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++的完整实现。