用于查找长度为k的第一个重复子串的算法
有一个我应该做的功课，我需要帮助。 我应该编写一个程序来查找长度为k的第一个子字符串，它至少在字符串中重复两次。
例如，在字符串“banana”中，有两个重复的长度为2的子字符串：“an”，“na”。 在这种情况下，答案是“an”，因为它早于“na”
请注意，简单的O（n ^ 2）算法没有用，因为程序的执行时间有时间限制，所以我猜它应该是线性时间。
还有一个提示：使用哈希表。
我不想要代码。 我只是想让你给我一点线索，因为我不知道如何使用散列表来实现这一点。 我是否也应该使用特定的数据结构？
迭代字符串（0，1，2，...）的字符索引直到并包括倒数第二个字符的索引（即，直到strlen（str） - 2）。 对于每次迭代，请执行以下操作...
从字符索引处提取2个字符的子字符串。
检查你的散列表是否包含2个字符的子字符串。 如果是这样，你已经得到了你的答案。
将每个2-char子串插入散列表。
这很容易修改以处理长度为k的子串。
将Will A的算法与滚动哈希相结合以获得线性时间算法。
您可以使用链接哈希映射。
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";
}
上一篇: Algorithm for finding first repeated substring of length k