42
правки
Изменения
Источники информации
Ясно, что никакой тандемный повтор не может встретиться больше чем в одной из этих подзадач. Первые две подзадачи решаются рекурсивно применением того же алгоритма Ландау-Шмидта. Две последние подзадачи симметричны, поэтому мы рассмотрим только третью подзадачу, и алгоритм для нее определит весь алгоритм.
{|border="0" cellpadding="2" width=30% align=right|[[Файл: tandem.png|thumb|400px|center| Любая позиция между <tex>A</tex> и <tex>B</tex> включительно может быть начальной точкой тандемного повтора длины <tex>2l</tex>. Как указывается в шаге 4, длины <tex>l_1</tex> и <tex>l_2</tex> обе положительны, поэтому подынтервал этих начальных точек определяет тандемные повторы, в которых первая копия покрывает <tex>h</tex>.]]|}
'''Алгоритм для задачи 3'''
Мы хотим найти все тандемные повторы, у которых первая копия покрывает позицию h (но не обязательно начинается в ней). Идея алгоритма заключается в следующем. Для любого фиксированного <tex>l</tex> можно за константное время проверить, существует ли такой тандемный повтор длины <tex>2l</tex>, у которого первая копия покрывает позицию <tex>h</tex>. Применение этого теста ко всем допустимым значениям <tex>l</tex> означает, что за время О(п) мы можем найти все длины таких тандемных повторов. Более того, для каждой такой длины мы можем перечислить начальные точки этих тандемных повторов за время, пропорциональное их числу. Ниже описано, как проверить
число <tex>l</tex>.
begin
# Положить <tex>q:=h + l</tex>.
# Вычислить наибольшее общее продолжение (в прямом направлении) из позиций <tex>h</tex> и <tex>q</tex>. Пусть <tex>l_1</tex> — длина этого продолжения.
# Вычислить наибольшее общее продолжение (в обратном направлении) из позиций <tex>h - 1</tex> и <tex>q - 1</tex>. Пусть <tex>l_2</tex> — длина этого продолжения.
# Тандемный повтор длины <tex>2l</tex>, первая копия которого покрывает позицию <tex>h</tex>, существует в том и только том случае, если <tex>l_1 + l_2 \geqslant l</tex> и обе длины <tex>l_1</tex> и <tex>l_2</tex> положительны. Более того, если такой тандемный повтор длины <tex>2l</tex> существует, то он может начинаться в любой позиции от <tex>max(h - l_2, h — l + 1)</tex> до <tex>min(h + l_1 — l, h)</tex> включительно. Вторая копия повтора начинается в <tex>l</tex> позициях вправо. Вывести каждую из этих начальных позиций вместе с длиной <tex>2l</tex>.
end.
== Теорема ==
{{Лемма
|proof=
То, что алгоритм находит все тандемные повторы, прямо следует из факта, что каждый тандем имеет форму, предусмотренную одной из подзадач 1 —4. Чтобы показать, что никакой тандемный повтор не выводится дважды, вспомним, что для <tex>h = n/2</tex> никакой из тандемов не принимает формы, предусмотренной более чем одной из четырех подзадач. Рекурсивно это выполняется для подзадач 1 и 2. Далее, при доказательстве Леммы мы установили, что решение подзадачи 3(а также 4) никогда не получает один и тот же тандем дважды. Следовательно, при полном решении четырех подзадач никакой тандемный повтор не выводится дважды. Отсюда следует, что время вывода всех тандемных повторов равно <tex>O(z)</tex>. Чтобы завершить анализ, рассмотрим время, расходуемое на запросы о продолжении. Это время пропорционально числу выполняемых запросов. Пусть <tex>T(n)</tex> — число запросов при длине строки <tex>n</tex>. Тогда <tex>T(n) = 2T(n/2) + 2n</tex> и <tex>T(n) = O(n \log n)</tex>, как и утверждалось.}}
== Источники информации ==
* Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. — 2-е изд.
