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