Решение самое быстрое (O(n)) и самое заумное: построить
суффиксное дерево, потом снизу вверх для каждой вершины найти индекс минимального и максимального по индексу листа в поддереве. Потом найти любую вершину, глубже 5, в которой минимальный и максимальный листы отстоят по крайней мере на глубину вершины (надо еще аккуратно обработать все вершины на ребре к отцу)
Более простое но и более медленное решение (за O(n^2)) - считайте полиномиальный хеш всех подстрок и храните в хешмапе минимальный индекс для каждого хеша. Оптять же, как только встретили подстроку, которую уже видели и ее первый индекс такой, что нет пересечения с текущей строкой - вы нашли ответ.
Еще за O(n^2) же есть решение через динамическое программирование: считайте F(i,j) - максимальная длина совпадающих строк, начинающихся с символов i и j (F(i,j) = 1 + F(i+1, j+1), если s[i] == s[j] и 0 иначе). Потом для каждой пары начал берите минимум из f(i,j), abs(j-i) - это и будет максимальная длина непересекающихся фрагментов с этих индексов. Если где-то нашли больше 5 - это ответ.
Ну и самое простое и медленное решение (за куб) - три цикла. Переберите 2 начала строк и сравнивайте их в цикле, пока они совпадают, не пересекаются и не выходят за границы строки. Если насчитали больше 5 символов - вы нашли ответ. Это почти как предыдущее решение, только без динамического программирования.
Простой
Средний
