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

Определение:

Тандемным повтором (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]).