高效最常用的后缀算法？

Question

我有几个GB值得的字符串，每个前缀我想找到10个最常见的后缀。有没有一个有效的算法呢？

一个显而易见的解决办法是：

• 商店排序<string, count>双名单。
• 通过二进制搜索范围标识我们正在搜索的前缀。
• 在这个范围内找到10个最高的count s。
• 可能预先计算所有短前缀，因此它不需要查看大部分数据。

我不确定这是否真的有效。有没有更好的方式我忽略了？

答案必须是实时的，但它可能需要尽可能多的预处理。

Answer 1

将单词放在树中，例如trie或radix，为每个完整单词放置一个“出现次数”计数器，这样您就知道哪些节点是结尾，以及它们有多普遍。

通过迭代找到前缀/后缀组合。

这两个操作都是O（n * k）其中k是最长单词的长度;这是作为散列表的same complexity。

HAT-trie是一个高速缓存意识的版本，可以保证高性能。