c++ - C++ 的后缀树库以及如何使用它的简单示例

Question

我正在搜索后缀树库(具有线性时间构造)，我找到的只是 PATL，但 PATL 没有文档，我无法找出任何示例。那么是否有一个具有良好文档的 C++ 后缀树库？

PATL 主页: http://code.google.com/p/patl/

编辑:
动机:我需要处理大量的字符串并找到频繁出现的公共(public)子字符串，并报告在 t 秒内是否出现了超过 n 次的任何子字符串。我实现了一棵树(节点中有计数器，实际上它不是计数器而是访问时间的 std::vector 因为就像我说的我需要时间)，但它非常慢。所以我想增加一定数量的消息(假设 30 秒的数据)，然后在该字符串上构建一个后缀树.

Answer 1

看看 SeqAn提供各种搜索算法和数据结构的高性能实现以及文档的库。

例如，suffix array类可以用作后缀树的直接替代品。

除此之外，您的问题本身听起来很复杂，我不确定您可以加快多少速度。用一般的措辞来说，这是一个 NP 难的多重对齐问题。您可能可以将其转换为更易于处理的内容，因为您只对精确的子匹配感兴趣，但它仍然很复杂。