接尾辞配列とLCP配列を使用して文字列のi番目の部分文字列を検索する方法は？

Question

私たちは辞書順で文字列のすべての明確なサブ文字列を手配し、我々はそれがsuffix arrayとLCP arrayだ使用して、それを見つけることが可能ですサブ

1）i番目の必要がある場合は？

2.）はいの場合、どうすればよいですか？時間複雑度がO（Nlog^2N）であるManber & Myersを使用して接尾辞配列を作成している間にO（Nlog^N）で行うことができます。 ）？

Answer 1

はいサフィックスアレイとLCPアレイを使用して実行できます。

接尾辞配列とLCP配列を計算する方法がわかっていると仮定します。

接尾辞配列lcp[]を示すp[]をLCP配列とする。

i'thランク接尾辞までの別個のサブストリングの数を格納する配列を作成します。これはこの式を使用して計算できます。ただ、累積配列cum[]にiの下限を見つけるi'thサブ文字列を見つけるために今すぐ

cum[0] = n - p[0]; 
for i = 1 to n do: 
    cum[i] = cum[i-1] + (n - p[i] - lcp[i]) 

を：詳細はHere

がcum[]は以下のように計算することができ、累積配列を示すものと見てくださいそれはあなたのサブ文字列がどこから始まって、長さまでのすべての文字を印刷するべきかのサフィックスのランクを与えるでしょう

i - cum[pos-1] + lcp[pos] // i lies between cum[pos-1] and cum[pos] so for finding 
          // length of sub string starting from cum[pos-1] we should 
          // subtract cum[pos-1] from i and add lcp[pos] as it is 
          // common string between current rank suffix and 
          // previous rank suffix. 

ここで、posは下限値の戻り値です。接尾辞配列、LCPの完全な実装のために

string ithSubstring(int i){ 
    pos = lower_bound(cum , cum + n , i); 
    return S.substr(arr[pos] , i - cum[pos-1] + lcp[pos]);// considering S as original character string 
} 

とロジックの上に、あなたはHere