algorithm - 查找文档中重复的语句

Question

假设有一个包含许多重复语句(如日志消息)的文档。例如 ( a b d c e a d) 将每个字母视为一个句子。

我们需要找出所有可能的唯一序列及其计数。例如(abd = 1 . bd = 1. ad = 1 等等)

我们得到了一个序列中可以包含的句子数量的最小值和最大值。

我们如何才能在空间和时间方面最有效地做到这一点？

我尝试分两步将其编码为树问题(找到可能的组合，然后计算)。我查看了后缀树，但空间复杂度可能很大，考虑到我们正在处理句子

Answer 1

我会做以下事情:

1. 将所有句子映射到整数(使用 HashMap )。

2. 为生成的整数数组构建后缀树/后缀数组/后缀自动机。