Алгоритм Крочемора

Материал из Викиконспекты
Версия от 02:51, 28 мая 2014; 188.227.78.59 (обсуждение) (Упрощенный алгоритм)
Перейти к: навигация, поиск
Определение:
Тандемным повтором (tandem repeat) в строке называются два вхождения какой-либо подстроки подряд. Иными словами, тандемный повтор описывается парой индексов [math]i \lt j[/math] такими, что подстрока [math]s[i \ldots j][/math] — это две одинаковые строки, записанные подряд.


Алгоритм Крочемора (Crochemore algorithm) позволяет найти все тандемные повторы в исходной строке [math]s[1..n][/math] за [math]O(n \cdot log (n))[/math].

Идея

Разобьем описание алгоритма на две части: сначала покажем упрощенный алгоритм, а затем попытаемся его оптимизировать, в итоге придя к нужному нам результату.

Упрощенный алгоритм

Рассмотрим следующую строку Фиббоначи:

1 2 3 4 5 6 7 8 9 10 11 12 13
[math]f_6 = [/math] a b a a b a b a a b a a b

Будем вычислять все повторяющиеся подстроки длиной [math]l[/math], где [math]l = 1 ... n - 1[/math], (здесь и далее [math]n = |s|[/math]).

Псевдокод

Реализация

Доказательство

Сложность

Источники