文字列の膨大なリスト (800 万から 1000 万) があります。ウィキペディアのページ タイトルです。これらの文字列に対してセットのようなデータ構造を作成した後、必要な操作はboolean contains(String str).
簡単な方法はHashSet、TreeSetまたは同様のものを使用することです（たとえば、Javaで）。
このユースケースにより適したデータ構造はありますか?
PS: ブルーム フィルターは使用できません。誤検知に対処したくありません。
1 に答える
1
constant-time よりもスペースを節約することに関心がcontains()あり、保存された文字列に多くの重複がある場合は、トライが役立つ場合があります。その場合、の長さは になりcontains(str)ます。O(n)nstr
于 2012-11-16T03:33:21.487 に答える