Algorithm for finding first repeated substring of length k

There is a homework I should do and I need help. I should write a program to find the first substring of length k that is repeated in the string at least twice.

For example in the string "banana" there are two repeated substrings of length 2: "an" , "na". In this case, the answer is "an" because it appeared sooner than "na"

Note that the simple O(n^2) algorithm is not useful since there is time limit on execution time of program so I guess it should be in linear time.

There is a hint too: Use Hash table.

I don't want the code. I just want you to give me a clue because I have no idea how to do this using a hash table. Should I use a specific data structure too?

---

Iterate over the character indexes of the string (0, 1, 2, ...) up to and including the index of the second-from-last character (ie up to strlen(str) - 2). For each iteration, do the following...

Extract the 2-char substring starting at the character index.

Check whether your hashtable contains the 2-char substring. If it does, you've got your answer.

Insert each 2-char substring into the hashtable.

This is easily modifiable to cope with substrings of length 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";
}

链接地址: http://www.djcxy.com/p/70658.html

上一篇: 查找给定字符串的主要循环子字符串

下一篇: 用于查找长度为k的第一个重复子串的算法