Для строки длины L я хочу найти самую длинную подстроку, которая появляется n (n < L) или более раз в строке.
Например, самая длинная подстрока, которая встречается 2 или более раз в "BANANA", является "ANA", начиная с индекса 1 и снова начиная с индекса 3. Подстрокам разрешено перекрываться.
В строке "FFFFFF" самая длинная строка, которая появляется 3 или более раз, это "FFFF".
Алгоритм грубой силы для n = 2 будет выбирать все пары индексов в строке, а затем работать до тех пор, пока символы не будут отличаться. Пролетная часть принимает O (L), а число пар - O (L ^ 2) (дубликаты не допускаются, но я игнорирую это), поэтому сложность этого алгоритма для n = 2 была бы O (L ^ 3). При больших значениях n это растет экспоненциально.
Существует ли более эффективный алгоритм для этой проблемы?
