Найдите самую длинную повторяющуюся строку и сколько раз она повторяется в данной строке

Question

Например, для заданной строки " abc fghi bc kl abcd lkm abcdefg " функция должна вернуть строку " abcd " и счетчик 2.

Решение O (n ^ 2) кажется простым, но я ищу лучшее решение.

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

Answer 1

Вы можете решить это за линейное время, построив дерево суффиксов и выбрав путь от корня до самого глубокого внутреннего узла; это даст вам самую длинную повторяемую строку. Если у вас есть эта строка, подсчитать, сколько раз она появляется, тривиально.

Answer 2

Конечный автомат может дать что-то лучше, чем big-O (N ^ 2).

РЕДАКТИРОВАТЬ: Дерево суффиксов, предложенное в другом ответе, является такой реализацией конечного автомата:)