5

私は、部分キーハッシュのアルゴリズムを書くように求められたインタビューに出演しました。ABCBC がハッシュに挿入されている場合、サブ文字列を検索すると、保存されている値が返されます。私の答えは、特定のキーのすべての可能な部分文字列のコレクションを作成し、各部分文字列とその 1 つ以上の親文字列との間のマッピングを維持することでした。次に、すべての部分文字列のコレクションの BST を維持します。各ノードは、その部分文字列が一致する可能性のある実際の値のコレクションを指します。たとえば。A、AB、ABC、ABCB、ABCBC、B、BC、BCB、BCBC、C、CB、CBC は、この文字列の可能な部分文字列です。BAB のような他の文字列もあるかもしれませんが、AB と B はその部分文字列です。したがって、AB を指定すると、BAB と ABCBC の 2 つの文字列にマップされます。

他のより効率的な方法はありますか？ありがとう

4

1 に答える 1

3

各部分文字列をハッシュに保存し、それが最終かどうか、可能な次の文字と前の文字をメモします。この部分文字列を途中に持つ可能性のあるすべての単語の前の文字と、この部分文字列を先頭に持つすべての単語の次の文字を保存します。

したがって、エントリ foraにはすべての単語が含まれている必要はありませんa。ただし、必要に応じてそのリストを作成するのは簡単です。また、挿入中に部分文字列のサイズが小さくなり、現在の継続で現在の部分文字列が既にあることがわかった場合は、停止できます。

同じ文字の単語がたくさんあると仮定すると、実際のリストの生成が遅くなるという代償を払って、スペースと挿入をいくらか節約できます。O(n*n)ただし、最悪の場合はn文字列の場合です。

削除するには、同様の手順に従い、他の部分文字列が入っている部分文字列で削除を停止します。

于 2012-05-26T17:55:09.933 に答える