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

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

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

Идея

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