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