2

接尾辞配列、つまり、辞書順で文字列のすべての接尾辞の開始位置を与える整数の配列を構築したとします。

例: stringstr=abcabbcaの場合、

サフィックス配列は次のとおりです。

suffixArray[] = [7 3 0 4 5 1 6 2]

説明：

i   Suffix      LCP of str and str[i..]   Length of LCP
7   a           a                           1
3   abbca       ab                          2
0   abcabbca    abcabbca                    8
4   bbca        empty string                0
5   bca         empty string                0
1   bcabbca     empty string                0
6   ca          empty string                0
2   cabbca      empty string                0

これが構築されたので、 （文字列自体）と他の各サフィックスの間の最長共通プレフィックス（LCP）の長さsuffixArrayを見つけたいと思います。それを行う最も効率的な方法は何ですか？str

4

1 に答える 1

4

あなたのコメントに基づいてSA、標準LCP配列だけでなく接尾辞配列にもアクセスできると仮定します。つまり、インデックス i>0 で、接尾辞の最も長い共通プレフィックスの長さSA[i]とその辞書式を示すデータ構造です。前身SA[i-1]は。

質問で説明されているように、文字 L を使用して、作成する特別な LCP 配列を参照します。文字 N を使用して、入力文字列の長さを示しますstr。

次に、できることは次のとおりです。

  1. str接尾辞配列内の位置を決定します。SAエントリを見つけるために線形にスクリーニングすることでこれを行うことができます0。(説明:strはstr位置 0 から始まる接尾辞です。したがって、0接尾辞配列のエントリとして表示する必要があります。)

  2. 見つかったエントリがインデックス k にあるとします。次にL[k]:=N、 を設定できます。これSA[k]は文字列自体であり、それ自体と共通の N 文字のプレフィックスを持っているためです。

  3. 次にL[k-1]:=LCP[k]、 andを設定できL[k+1]:=LCP[k+1]ます。これは、標準の LCP がそのように定義されているためです。

  4. 次に、i:=k-2 から 0 までさかのぼって設定します。

    L[i] := min(LCP[i+1],L[i+1])

    これが機能するのは、各反復 i で、LCP[i+1]隣接する接尾辞SA[i]およびの最長の共通接頭辞がわかり、以前に処理された接尾辞と入力文字列の最長の共通接頭辞がわかるからです。は、接頭辞が と共通する長さを示し、 と共通する接頭辞より長くすることはできないため、これら 2 つの最小値でなければなりません。そうしないと、接尾辞配列内の位置が k に近くなります。SA[i+1]L[i+1]SA[i+1]strL[i]L[i]SA[i]strSA[i+1]

  5. また、i:=k+2 から N まで順方向にカウントして設定します

    L[i] := min(LCP[i],L[i-1])

    同じ理屈に基づいています。

次に、すべての N 個の値Lが設定され、配列へのランダム アクセスと整数比較がそれぞれ O(1) であると仮定すると、O(N) 時間しかかかりませんでした。

計算する配列の長さは N エントリであるため、O(N) の複雑さが最適です。

(注。ステップ 4 と 5 のループをそれぞれ k-1 と k+1 で開始し、ステップ 3 を取り除くことができます。余分なステップは、説明を行うためだけに役立ちます。 .)

于 2012-06-19T07:26:12.563 に答える