Алгоритм Крочемора — различия между версиями
(Новая страница: «{{Определение |definition = '''Тандемным повтором''' (tandem repeat) в строке называются два вхождения к...») |
(нет различий)
|
Версия 02:29, 28 мая 2014
Определение: |
Тандемным повтором (tandem repeat) в строке называются два вхождения какой-либо подстроки подряд. Иными словами, тандемный повтор описывается парой индексов | такими, что подстрока — это две одинаковые строки, записанные подряд.
Алгоритм Крочемора (Crochemore algorithm) позволяет найти все тандемные повторы в исходной строке за .
Содержание
Идея
Разобьем описание алгоритма на две части: сначала покажем упрощенный алгоритм, а затем попытаемся его оптимизировать, в итоге придя к нужному нам результату.