我已经搜索过有关此问题的帖子。但他们都没有明确的答案。
查找给定字符串中长度为 n 的最常见子字符串的出现次数。 例如“deded”，我们将子字符串的长度设置为3。“ded”将是最常见的子字符串，出现次数为2。 很少有帖子建议使用后缀树，时间复杂度为 O(nlgn)，空间复杂度为 O(n)。 首先，我对后缀树不熟悉。我的想法是用hashmap存储每个长度为3的子串的出现次数。时间是O(n)，空间也是O(n)。这比后缀树好吗？我应该考虑 HashMap 碰撞吗？
补充:如果解决了上述问题，如何解决子串长度不重要的问题。只需找到给定字符串中最常见的子字符串即可。
最佳答案
如果最常见的子字符串的长度并不重要(但假设您希望它大于 1)，那么最好的解决方案是查找长度为 2 的最常见的子字符串。您可以使用线性时间内的后缀树，如果你查找后缀树，那么就会清楚如何做到这一点。如果您希望最常见子字符串的长度 M 作为输入参数，那么您可以使用乘加哈希法在线性时间内对长度为 M 的所有子字符串进行哈希处理，其中将前一个字符串哈希值乘以一个常数，然后添加字符串中下一个最低有效值的值，并取以素数 P 为模的模数。如果您将计算的字符串整数的模数 P 选择为随机选择的素数 P，这样您就可以存储 O(P) 内存，那么如果您假设您的散列没有冲突，那么这将在线性时间内完成任务。如果你假设你的哈希可能有很多冲突，并且子字符串的长度为 M，总字符串长度为 N，那么运行时间将是 O(MN)，因为你必须检查所有冲突，这在最坏的情况下case 可以检查长度为 M 的所有子字符串，例如，如果您的字符串是全部由一个字符组成的字符串。后缀树在最坏的情况下会更好，如果您想要一些详细信息(但不完全，因为后缀树很复杂)，请告诉我，我可以在较高层次上解释如何使用后缀树获得更快的解决方案。
关于string - 找到给定字符串中最常见的子字符串？允许重叠，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26106081/