寻找长度为 k 的第一个重复子串的算法

Question

有一个作业我应该做，我需要帮助。我应该编写一个程序来找到长度为 k 的第一个子字符串，该子字符串在字符串中至少重复两次。

例如在字符串“banana”中有两个长度为 2 的重复子串:“an”、“na”。在这种情况下，答案是“an”，因为它出现得比“na”早

请注意，简单的 O(n^2) 算法没有用，因为程序的执行时间有时间限制，所以我想它应该是线性时间。

还有一个提示:使用哈希表。

我不想要代码。我只是想让你给我一个线索，因为我不知道如何使用哈希表来做到这一点。我也应该使用特定的数据结构吗？

Answer 1

迭代字符串的字符索引 (0, 1, 2, ...) 直到并包括倒数第二个字符的索引(即直到 strlen(str) - 2)。对于每次迭代，执行以下操作...

从字符索引开始提取 2 个字符的子字符串。

检查您的哈希表是否包含 2 个字符的子字符串。如果是这样，您就有了答案。

将每个 2 个字符的子字符串插入哈希表。

这很容易修改以应对长度为 k 的子串。