Udi Manber and Gene Myers Method

Question

I have a suffix array SA, and an array L that stores the length of LCP (longest common prefix) between two consecutive suffixes, i.e.

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

It's also described here.

How should I use this array L to find the LCP(x,y) between given two suffixes x and 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 

Here array height is equal to array L

using array sa , we can easily calculate array rank

Then using Sparse Table (ST) algorithm to calculate rmq question. 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)]);
}

Then just call the function lcp(). Time and space is O(nlogn)