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

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

Например, в строке «банан» есть две повторяющиеся подстроки длины 2: «an», «na» . В этом случае ответ - «an», потому что он появился раньше, чем «na»

. Обратите внимание, что простой алгоритм O (n ^ 2) бесполезен, поскольку существует ограничение по времени выполнения программы, поэтому я думаю, что он должен быть в линейном времени.

Также есть подсказка: используйте хеш-таблицу.

Мне не нужен код. Я просто хочу, чтобы вы дали мне подсказку, потому что я понятия не имею, как это сделать с помощью хеш-таблицы. Следует ли мне также использовать определенную структуру данных?