C++ FP树或前缀树

Question

我有一些这样的序列

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

在C + +中有一些有效的实现前缀树或fp树或类似的吗？

Answer 1

我不明白你在说什么..。但是如果你需要构建FP树，这里是我找到的最好的页面

FP Tree Algorithm

Answer 2

不清楚您到底拥有什么，因为给定的数据似乎没有采用任何标准表示法。

如果前缀只是整数值之间的几个共享的初始十进制数字，它们可能不会对数据存储产生任何重大影响。您可以在向数据结构中插入值之前减去100，将值存储为char，然后在检索后再加100，但这样做可能不值得。

也许您应该将序列存储为对vector元素进行排序的std::deque< std::vector< int > >。除非有一种我看不到的模式，或者我曲解了问题，否则在寻找包含给定数量的序列时，最佳性能必须是序列数量中的O(N)乘以序列长度中的O(lg N)。