В общем, я нашёл статью (2014 года), где за линейное время решается такая задача: назовём подстроку k-максимальной, если она встречается не менее k раз и не является подстрокой никакой другой подстроки, встречающейся минимум k раз. Найти _все_ максимальные подстроки.

Нашу задачу я бы переформулировал так: дано k, найти максимальную _длину_ подстроки, встречающейся как минимум k раз. Она проще, есть даже в книжке Седжвика по алгоритмам в качестве задачи (но там не указана асимптотика).

Единственное что раньше вечера пятницы я это не напишу, потому что у меня завтра и послезавтра адские лекции у студентов в духе "взял интеграл ? положи его на место !". Могу скинуть статью, если хочешь (но там overkill, конечно).