Изменения
Нет описания правки
{{Определение
|definition =
'''Тандемным повтором''' (англ. "'tandem repeat"') в строке называются два вхождения какой-либо подстроки подряд. Иными словами, тандемный повтор описывается парой индексов <tex>i < j</tex> такими, что подстрока <tex>s[i \ldots j]</tex> {{---}} это две одинаковые строки, записанные подряд
}}
'''Алгоритм Крочемора''' (англ. "'crochemore algorithm"') {{---}} алгоритм на строках, позволяющий найти все тандемные повторы в строке <tex>s[1..n]</tex> за <tex>O(n \log n)</tex>
== Алгоритм ==
Разобьем описание алгоритма на две части: сначала покажем упрощенный алгоритм, работающий за <tex>O(n^2)</tex>, а затем попытаемся его оптимизировать до <tex>O(n \log n)</tex>
=== Упрощенный алгоритм ===
Рассмотрим следующую строку Фиббоначи:
Если реализовывать процесс декомпозиции "наивно", то поучаем сложность <tex>O(n^2)</tex>
=== Оптимизация ===
Декомпозицию каждой последовательности можно получить косвенным путем, а не путем прямых вычислений. Идея такого подхода состоит в следующем:
Поскольку строка <tex>s</tex> содержит <tex>n</tex> позиций, то из предыдущей леммы следует, что всего в малых последовательностях на всех уровнях содержится <tex>O(n \log n)</tex> позиций. Таким образом, если время обработки последовательностей на каждом уровне <tex>l</tex> пропорционально количеству элементов в малых последовательностях этого уровня, то полный процесс декомпозиции будет выполнен за <tex>O(n \log n)</tex>, чего мы и хотели получить.
== Псевдокод ==
crochemore()
<tex>l</tex> <tex>\gets</tex> 1
l++
Найдем малые последовательности на уровне <tex>l</tex>
== Источники информации ==
