C ++ FP-Treeまたはプレフィックスツリー

Question

これらのようないくつかのシーケンスがあります

(100) - (102) - (103) - (104,106) - (108)
(101) - (103)
(102) - (106)

C + +には、プレフィックスツリーまたはFP-Treeなどの効率的な実装がありますか？

Answer 1

何を言っているのかわかりません...しかし、ここにFPツリーを構築する必要がある場合は、私が見つけた最高のページです

FPツリーアルゴリズム

Answer 2

与えられたデータが標準表記にないように見えるため、あなたが持っているものを正確に明確にしていません。

接頭辞が、整数値間でいくつかの共有初期桁である場合、おそらくデータストレージに大きな違いをもたらさないでしょう。差し引くことができます 100 データ構造に値を挿入する前に、値を次のように保存します char, 、そして検索後に100を追加しますが、おそらく努力する価値はありません。

おそらく、一連のシーケンスをとして保存する必要があります std::deque< std::vector< int > > どこ vector 要素がソートされます。私が見ることができないパターンや問題を誤って解釈している場合を除き、どのシーケンスを含むシーケンスがシーケンスの数の数にo（n）でなければならないことを見つけるのに最適なパフォーマンスは、シーケンス長のo（lg n）である必要があります。