0

説明してください：

n 文字のテキストに対応するサフィックス配列があり、m 文字のパターンのテキスト内のすべての出現箇所を検索したいとします。接尾辞は順序付けられているため、最も簡単な解決策は、O(log n) 比較を使用してパターンの最初と最後の出現 (存在する場合) をバイナリ検索することです。

pattern の最初と最後の出現を決定した後、 pattern のすべての出現を取得する方法を知る必要があります。

4

1 に答える 1

1

あなたが引用したテキストは、次の 2 つの点でやや混乱しており、おそらく誤解を招く可能性さえあります。

  1. パターンの最初と最後の出現を見つけるだけで十分だと言っていますが、より正確には、接尾辞配列内のパターンの最初と最後の出現を見つける必要があります。これは、下にあるテキストの最初と最後の出現と同じではありません。

  2. O(log n) の比較が必要だと言っています。これは、「比較」が m 文字までの文字列比較を参照する場合にのみ当てはまります。最大 m 文字の比較には O(m) の時間がかかるため、計算ステップの数 (たとえば、標準 RAM モデル) は O(m*log n) です。LCP (longest-common-prefix) 配列などの補助データ構造を構築して使用すると、改善される可能性があります。

ここで、あなたの質問に答えるために: 上記の (1.) を考慮に入れると、サフィックス配列が辞書順に並べ替えられているため、パターンのすべての出現を簡単に取得できます。これは、最初の出現が辞書編集的に最小であり、最後の出現が辞書編集的に最大であることを意味します。したがって、残りのオカレンスは最初と最後の間にある必要があります。

例。文字列を考えてみましょうbcfabcabxbbcabcgdebcd。その接尾辞配列 (接尾辞の開始位置として表され、0 から数えます) は次のとおりです。

[3, 12, 6, 9, 10, 4, 18, 0, 13, 7, 11, 5, 19, 1, 14, 20, 16, 17, 2, 15, 8]

これは、次のサフィックスのリストに対応します。

3  : abcabxbbcabcgdebcd
12 : abcgdebcd
6  : abxbbcabcgdebcd
9  : bbcabcgdebcd
10 : bcabcgdebcd            <======= first occurrence of 'bc'
4  : bcabxbbcabcgdebcd
18 : bcd
0  : bcfabcabxbbcabcgdebcd
13 : bcgdebcd               <======= last occurrence of 'bc'
7  : bxbbcabcgdebcd
11 : cabcgdebcd
5  : cabxbbcabcgdebcd
19 : cd
1  : cfabcabxbbcabcgdebcd
14 : cgdebcd
20 : d
16 : debcd
17 : ebcd
2  : fabcabxbbcabcgdebcd
15 : gdebcd
8  : xbbcabcgdebcd

探しているパターンが「bc」であるとします。接尾辞配列でそのパターンの最初と最後の出現をマークしました。辞書順ソートのため、その間にあるすべてのエントリも 'bc' で始まる必要があり、'bc' で始まるエントリはその中間にある必要があります。したがって、「bc」で始まるすべての接尾辞、つまり「bc」が出現するすべての位置は、この最初と最後の出現の間にある必要があります。

位置整数として表される、特定した範囲は次のとおりです。

[10, 4, 18, 0, 13]

したがって、位置 10、4、18、0、および 13 は、パターンの発生を示します。

(実際には、サフィックスの完全な文字列リストは使用されず、整数位置リストのみが使用されることに注意してください。)

于 2012-08-14T02:08:44.803 に答える