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

Question

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

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

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

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

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

Answer 1

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

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

检查您的哈希表是否包含 2 个字符的子字符串。如果是的话，你就得到了答案。

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

这很容易修改以处理长度为 k 的子串。

Answer 2

将 Will A 的算法与滚动哈希相结合，得到线性时间算法。

Answer 3

您可以使用链接哈希图。

public static String findRepeated(String s , int k){
    Map<String,Integer> map = new LinkedHashMap<String,Integer>();
    for(int i = 0 ; i < s.length() - k ; i ++){
        String temp = s.substring(i,i +k);
        if(!map.containsKey(temp)){
            map.put(temp, 1);
        }
        else{
            map.put(temp, map.get(temp) + 1);
        }
    }
    for(Map.Entry<String,Integer> entry : map.entrySet()){
        if(entry.getValue() > 1){
            return entry.getKey();
        }
    }
    return "no such value";
}