Omi*_*mid 5 string algorithm hash substring data-structures
我应该做一些功课,我需要帮助.我应该编写一个程序来查找长度为k的第一个子串,该子串在字符串中重复至少两次.
例如,在字符串"banana"中,存在两个长度为2的重复子串:"an","na".在这种情况下,答案是"一个",因为它似乎比"na"更早出现
请注意,简单的O(n ^ 2)算法没有用,因为程序的执行时间有时间限制,所以我猜它应该是线性时间.
还有一个提示:使用哈希表.
我不想要代码.我只是想让你给我一个线索,因为我不知道如何使用哈希表来做到这一点.我也应该使用特定的数据结构吗？
迭代字符串的字符索引 (0, 1, 2, ...)，直到并包括倒数第二个字符的索引（即直到 strlen(str) - 2）。对于每次迭代，执行以下操作...
提取从字符索引开始的 2 字符子字符串。
检查您的哈希表是否包含 2 个字符的子字符串。如果是的话，你就得到了答案。
将每个 2 个字符的子字符串插入哈希表中。
这很容易修改以处理长度为 k 的子串。