algorithm - Udi Manber 和 Gene Myers 方法

Question

我有一个后缀数组SA，和一个存储LCP长度的数组L两个连续后缀之间的(最长公共(public)前缀)，即

L[i]=LCP(SA[i-1],SA[i]) where 1<=i<=|SA|

还描述了here .

我应该如何使用这个数组 L 来找到给定的两个后缀 x 和 y 之间的 LCP(x,y)？

Answer 1

rank[0...7]: 4 6 8 1 2 3 5 7 
string:      a a b a a a a b 
------------------------------------------- 
 sa[1] = 3 : a a a a b         height[1] = 0 
 sa[2] = 4 : a a a b           height[2] = 3 
 sa[3] = 5 : a a b             height[3] = 2 
 sa[4] = 0 : a a b a a a a b   height[4] = 3 
 sa[5] = 6 : a b               height[5] = 1 
 sa[6] = 1 : a b a a a a b     height[6] = 2 
 sa[7] = 7 : b                 height[7] = 0 
 sa[8] = 2 : b a a a a b       height[8] = 1 

此处数组高度等于数组L

使用数组 sa ，我们可以轻松计算数组 rank

然后使用稀疏表(ST)算法计算rmq问题。 http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Range_Minimum_Query_%28RMQ%29

int *RMQ = height;
//int RMQ[N];
int mm[N];
int best[20][N]; //best[i][j] means the minimal value in the range [j, j + 2^i)
void initRMQ(int n){
  int i,j,a,b;
  for(mm[0]=-1,i=1;i<=n;i++)
  mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
  for(i=1;i<=n;i++) best[0][i]=i;
  for(i=1;i<=mm[n];i++)
  for(j=1;j<=n+1-(1<<i);j++){
    a=best[i-1][j];
    b=best[i-1][j+(1<<(i-1))];
    if(RMQ[a]<RMQ[b]) best[i][j]=a;
    else best[i][j]=b;
  }
}
int askRMQ(int a,int b){
  int t;
  t=mm[b-a+1];b-=(1<<t)-1;
  a=best[t][a];b=best[t][b];
  return RMQ[a]<RMQ[b]?a:b;
}
int lcp(int a,int b){ //this is your answer
  int t;
  a=rank[a];b=rank[b];
  if(a>b) {t=a;a=b;b=t;}
  return(height[askRMQ(a+1,b)]);
}

然后只需调用函数 lcp()。时间和空间是O(nlogn)