Я ищу эффективный алгоритм, чтобы найти самый длинный повторяющийся образец в строке.
Например, рассмотрим следующую строку чисел:
5431428571428571428571428571427623874534
,
Как видите, 142857142857
это самый длинный шаблон, который повторяется в этой строке пару раз (по крайней мере, дважды).
Повторяющаяся строка не должна содержать каких-либо идей, а не грубой силы?
142857
это не самое длинное, потому что142857142857
оно длиннее. Я думаю, что вы должны отредактировать вопрос, чтобы уточнить, что вы подразумеваете под «повторяющимся шаблоном».Ответы:
Проблема на удивление нетривиальна. Во-первых, два алгоритма грубой силы. Квадрат («повторяющийся шаблон») определяется его длиной и позицией , и для его проверки требуется время . Если мы переберем все и , мы получим алгоритм . Мы можем улучшить это, сначала зацикливая на , а затем сканируя строку с двумя бегущими указателями на расстоянии . Таким образом, можно проверить, существует ли квадрат длины за линейное время, давая общее время работы .ℓ п O ( ℓ ) ℓ п O ( n3) ℓ ℓ 2 ℓ O ( n2)
Колпаков и Кучеров разработали алгоритм нахождения всех максимальных повторов в слове за время [1], и их алгоритм можно использовать для нахождения всех максимальных квадратов за время . Повтор подслово вида , где и является собственным префиксом . Самый большой квадрат, содержащийся в этом повторении: . Используя эту формулу, учитывая все максимальные повторения в слове (из которых только много), можно найти самый большой квадрат.O ( n ) O ( n ) весКИкс k ≥ 2 Икс вес ( ш⌊ к / 2 ⌋)2 O ( n )
[1] Колпаков Р., Кучеров Г. (1999). Нахождение максимальных повторений в слове за линейное время . В Основы информатики, 1999. 40-й ежегодный симпозиум (стр. 596-604). IEEE.
источник