Алгоритм нахождения первой повторяющейся подстроки длины k

Question

Мне нужно сделать домашнее задание, и мне нужна помощь. Я должен написать программу, чтобы найти первую подстроку длины k, которая повторяется в строке по крайней мере дважды.

Например, в строке «банан» есть две повторяющиеся подстроки длины 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";
}