algorithm - Udi Manber和Gene Myers方法

我有一个后缀数组sa和一个数组l，在两个连续的后缀之间存储LCP（最长的公共前缀）的长度，即。

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

它也被描述为here。
我应该如何使用这个数组l来查找给定两个后缀x和y之间的lcp（x，y）？

最佳答案

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可以方便地计算数组的秩
然后利用稀疏表（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）