Найдите самую длинную повторяющуюся строку и сколько раз она повторяется в данной строке
Например, если задана строка "abc fghi bc kl abcd lkm abcdefg", функция должна вернуть строку "abcd" и счетчик 2.
Решение A O(n^2) кажется простым, но я ищу лучшее решение.
Отредактировано: если нет ничего лучше, чем O (n ^ 2), то какой подход будет наилучшим с точки зрения производительности.
2 ответа
Решение
Вы можете решить это за линейное время, построив дерево суффиксов и выбрав путь от корня до самого глубокого внутреннего узла; это даст вам самую длинную повторяемую строку. Если у вас есть эта строка, подсчитать, сколько раз она появляется, тривиально.
Конечный автомат мог бы дать что-то лучше, чем big-O(N^2).
РЕДАКТИРОВАТЬ: Дерево суффиксов, предложенное в другом ответе, является такой реализацией конечного автомата:)