Изменения
Нет описания правки
{{Определение
|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)</tex>.
Далее для <tex>l = 2</tex> мы хотим найти все повторяющиеся подстроки длины <tex>2</tex>. Поскольку повторяющиеся подстроки длины <tex>l \geq geqslant 2</tex> будут иметь общий префикс длиной <tex>l - 1</tex>, то вычисления уровня <tex>l</tex> должны привести к последовательностям, которые будут подпоследовательностями последовательностей, вычисленных на уровне <tex>l - 1</tex>. Другими словами, разбиение на уровне <tex>l \geq geqslant 2</tex> {{---}} декомпозиция разбиения на уровне <tex>l - 1</tex>:
{|class="wikitable" style="text-align:center"
Декомпозицию каждой последовательности можно получить косвенным путем, а не путем прямых вычислений. Идея такого подхода состоит в следующем:
на каждом уровне <tex>l</tex> выполняется непосредственная декомпозиция каждой последовательности <tex>c^{(l)}_j</tex>. Более точно, если <tex>c^{(l)}_j = <\langle p_1, p_2, \ldots , p_r>\rangle</tex>, то необходимо проверить совпадение букв <tex>s[p_1 + l], s[p_2 + l], \ldots, s[p_r + l]</tex>, и, если какие-либо пары букв <tex>s[p_i + l]</tex> и <tex>s[p_j + l]</tex> равны, то <tex>p_i</tex> и <tex>p_j</tex> помещаются в одну и ту же последовательность на уровне <tex>l + 1</tex>.
Для каждой позиции <tex>p_i > 1</tex> известно, что подстрока <tex>s[p_i - 1 \ldots p_i + l - 1]</tex> (длиной <tex>l + 1</tex>) относится к некоторой последовательности <tex>c^{(l + 1)}_{j'}</tex> на уровне <tex>l + 1</tex>. Поскольку последовательность <tex>c^{(l)}_{j}</tex> соответствует уникальной подстроке строки <tex>s</tex>, то каждая такая последовательность <tex>c^{(l + 1)}_{j'}</tex> должна формироваться из тех же позиций <tex>p_{i_1}, p_{i_2}, \ldots , p_{i_k}</tex> последовательности <tex>c^{(l)}_{j}</tex>, которые определяют класс эквивалентности
<tex>s[p_{i_1} - 1] = s[p_{i_2} - 1] = \ldots = s[p_{i_k} - 1]</tex>.
= Источники =
* ''Билл Смит'' '''Методы и алгоритмы вычислений на строках'''. Пер. с англ. — {{---}} М.:Издательский дом "Вильямс", 2006. ISBN 5-8459-1081-1* [http://e-maxx.ru/algo/string_tandems E-maxx — {{---}} Поиск всех тандемных повторов в строке. Алгоритм Мейна-Лоренца]
[[Категория: Поиск тандемных повторов]]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Дискретная математика и алгоритмы]]
