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

9

Я ищу эффективный алгоритм, чтобы найти самый длинный повторяющийся образец в строке.

Например, рассмотрим следующую строку чисел:

5431428571428571428571428571427623874534,

Как видите, 142857142857это самый длинный шаблон, который повторяется в этой строке пару раз (по крайней мере, дважды).

Повторяющаяся строка не должна содержать каких-либо идей, а не грубой силы?

Юхо
источник
3
Вы не определили, что означает «пару раз», но если «дважды» считается «пару раз», то 142857это не самое длинное, потому что 142857142857оно длиннее. Я думаю, что вы должны отредактировать вопрос, чтобы уточнить, что вы подразумеваете под «повторяющимся шаблоном».
Tsuyoshi Ito
очень хороший момент. Я обновлю вопрос.
8
Требуете ли вы, чтобы вхождения шаблона не отличались друг от друга? Потому что, если нет, 142857142857 еще не самое длинное повторение; 142857142857142857142 встречается дважды. В любом случае, обычный ответ на такие вопросы - «деревья суффиксов».

Ответы:

15

Проблема на удивление нетривиальна. Во-первых, два алгоритма грубой силы. Квадрат («повторяющийся шаблон») определяется его длиной и позицией , и для его проверки требуется время . Если мы переберем все и , мы получим алгоритм . Мы можем улучшить это, сначала зацикливая на , а затем сканируя строку с двумя бегущими указателями на расстоянии . Таким образом, можно проверить, существует ли квадрат длины за линейное время, давая общее время работы .пО()пО(N3)2О(N2)

Колпаков и Кучеров разработали алгоритм нахождения всех максимальных повторов в слове за время [1], и их алгоритм можно использовать для нахождения всех максимальных квадратов за время . Повтор подслово вида , где и является собственным префиксом . Самый большой квадрат, содержащийся в этом повторении: . Используя эту формулу, учитывая все максимальные повторения в слове (из которых только много), можно найти самый большой квадрат.О(N)О(N)весКИксК2Иксвес(весК/2)2О(N)


[1] Колпаков Р., Кучеров Г. (1999). Нахождение максимальных повторений в слове за линейное время . В Основы информатики, 1999. 40-й ежегодный симпозиум (стр. 596-604). IEEE.

Юваль Фильмус
источник