3

文字列 S を保持し、次のことを可能にするデータ構造を必要とする問題に遭遇しました。

  1. 単語 W が S のサブワードかどうかを O(|W|) 時間でチェックする
  2. 与えられた単語 U のプレフィックスでもある S の最長のサフィックスを O(|U|) 時間で見つけます
  3. O(|K|) 時間で S の末尾に文字列 K を追加します

Ukkonen アルゴリズムによって構築された接尾辞ツリーが探しているものであることがわかりました。アルゴリズムは「接尾辞ツリーのオンライン構築」として説明されており、「オンライン」部分に問題があります。各文字アルゴリズムの挿入後、最終ステップで明示的に変換できる暗黙的な接尾辞ツリーを構築します。しかし、そのステップの前に暗黙的なツリーを検索に使用したい場合はどうすればよいでしょうか? 「オンライン」は、分析された文字列のプレフィックスを挿入した後に可能であることを示唆していますが、暗黙的なツリーで動作する最も単純なアルゴリズムの例さえ見つかりません。

私の質問は次のとおりです。暗黙の接尾辞ツリーで文字列を検索するにはどうすればよいですか?

編集:私は私の問題を解決する非常に良い答えを受け入れましたが、その間に私は2へのより簡単な解決策を見つけることができました:長さ|U|のSの接尾辞でUを検索するだけで十分です KMP アルゴリズムを使用し、最後に一致した文字数は文字列の重複になります。

4

1 に答える 1

3

暗黙的なサフィックス ツリーと明示的なサフィックス ツリーの違いは 1 つだけです。それは、文字列の終わりのマーカーを含まない (そして、これらの文字列の終わりのマーカーに対応するブランチを含まない) ことです。

これは、部分文字列を検索する場所に違いがないことを意味します - 暗黙的な接尾辞ツリーでも明示的な接尾辞ツリーでも。暗黙的な接尾辞ツリーには不要な分岐が少ないため、これにより、部分文字列検索のアルゴリズムがさらに効率的 (ただし線形時間) になることが保証されます。

したがって、要件 1 は自動的に満たされます。ルートからサフィックス ツリーを検索し、指定された単語に一致するブランチを選択するだけです。

要件 2 については、同じ暗黙的なサフィックス ツリーでは満たせないと思います。サフィックスを操作するには、文字列の終わりのマーカーが必要だからです。

O(|U|)ただし、特定の単語に対して別の（明示的な）接尾辞ツリーを使用すると、間に合うように実行できますU。秘訣は、接尾辞ツリーを作成する前に、この単語を逆にすることです。Sのプレフィックスでもあるの最長サフィックスを見つけるにはU、この別のサフィックス ツリーを使用して、逆文字列Sのサフィックスでもある逆文字列の最長プレフィックスを見つけますU。このサフィックス ツリーをルートから検索し、反転した文字列Sに一致するブランチを選択し、文字列の終わりのマーカーで最新のノードを覚えておいてください。次に、ルートからこのノードまでのパス上の文字列を逆にします (または、このパスの長さを決定し、末尾から同じ長さの部分文字列をコピーしますS)。

于 2013-01-11T11:39:01.803 に答える