algorithm - ウディ・マンバーとジーン・マイヤーズ法

Question

サフィックス配列 SA と、2 つの連続するサフィックス間のLCP (最長共通プレフィックス) の長さを格納する配列 L があります。

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

こちらにも記載されています。

この配列 L を使用して、指定された 2 つのサフィックス 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を使用すると、配列ランクを簡単に計算できます

次に、スパース テーブル (ST) アルゴリズムを使用してrmq questionを計算します。 http://community.topcoder.com/tc?module=静的&d1=チュートリアル&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)