我有几 GB 的字符串，对于每个前缀，我想找到 10 个最常见的后缀。是否有有效的算法？
一个明显的解决方案是:
- 存储
<string, count>的排序列表对。 - 通过二进制搜索范围识别我们正在搜索的前缀。
- 找到 10 个最高的
count在这个范围内。 - 可能为所有短前缀预先计算它，因此它永远不需要查看大部分数据。
我不确定这是否真的有效。有没有我忽略的更好的方法？
答案必须是实时的，但可以根据需要进行尽可能多的预处理。
最佳答案
将单词放在树中，例如trie或 radix ，为每个完整单词放置一个“出现次数”计数器，这样您就知道哪些节点是结尾以及它们有多常见。
通过迭代查找前缀/后缀组合。
这两个操作都是 O(n*k) 其中 k 是最长单词的长度；这是 same complexity作为哈希表。
HAT-trie 是一个缓存敏感的版本，可以保证高性能。
关于algorithm - 高效最常见的后缀算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2987563/