線形検索をしないでC内の高速二足語

Question

線形検索を使わずにCで高速双曲線（String => Pointer and Int => Pointer）を作るにはどうすればよいですか？ライブラリではなく、コードをいくつか（またはそれ以上）必要とし、クローズドソースソフトウェア（LGPLなど）で使用できるようにする必要があります。

Answer 1

Hash Tableを使用してください。ハッシュテーブルには一定時間の検索があります。 Here are some excerpts in Cおよびan implementation in C (and Portuguese :)。

Answer 2

ハッシュコードを使用してオブジェクトを格納するHash Tableを実装する必要があります。ルックアップ時間は一定です。

Binary Tree横断しログ（N）時間の要素を検索することができます。

Answer 3

Ternary Search Treeはこの使命のために生まれました。

Answer 4

文字列が長い場合は、「ハッシュテーブル」を一定時間と見なすことはできません。実行時は文字列の長さに依存します！長い文字列の場合、これは問題を引き起こします。さらに、テーブルが小さすぎたり、ハッシュ関数が貧弱すぎたりすると、衝突の問題が発生します。

ハッシュを使用する場合は、karp-rabinをご覧ください。あなたが探している単語のサイズに完全に依存するアルゴリズムを望むなら、aho-corasickを見てください。