42
правки
Изменения
→Корректность
{{Лемма
|statement = Приведенный метод корректно решает подзадачу 3 для фиксированного <tex>h</tex> Это значит, что он находит все тандемные повторы, у которых первая копия покрывает позицию <tex>h</tex>. Для фиксированного <tex>h</tex> его время работы 3й подзадачи равно <tex>O( n/2) + z_h</tex>, где <tex>z_h</tex> — число таких тандемных повторов.
|proof =
Предположим сначала, что имеется тандемный повтор, у которого первая копия покрывает позицию h, и его длина равна, скажем, <tex>2l</tex>. Это означает, что позиция <tex>q = h + l</tex> во второй копии соответствует позиции <tex>h</tex> в первойx копии. Следовательно, для того чтобы обеспечить совпадение суффиксов в этих копиях, некоторая подстрока, начинающаяся в <tex>h</tex>, должна совпадать с подстрокой, начинающейся в <tex>q</tex>. Такая подстрока может иметь длину не более <tex>l_1</tex>. Аналогично, должна быть подстрока, кончающаяся в <tex>h - 1</tex>, которая совпадает с подстрокой, кончающейся в <tex>q-1</tex>, для того чтобы обеспечить совпадение префиксов. Длина этой подстроки не должна превосходить <tex>l_2</tex>. Так как все символы между <tex>h</tex> и <tex>q</tex> содержатся в одной из двух копий, то <tex>l_1 + l_2 \geqslant l</tex>. Обратно, рассуждая в основном так же, если <tex> l_1 + l_2 \leqslant l </tex> и <tex>l_1</tex> и <tex>l_2</tex> положительны, то можно найти тандемный повтор длины <tex>2l</tex>, у которого первая копия покрывает <tex>h</tex>. Необходимое и достаточное условие существования такого тандема теперь доказано.
Обратное доказательство, что все начальные позиции попадают в названный диапазон, аналогично доказывается.
Для подсчета времени сначала отметим, что при фиксированном <tex>h</tex> методу нужно константное время на один выбор <tex>l</tex> для того, чтобы выполнить общие запросы о продолжении, и, таким образом, время <tex>O( n/2)</tex> на все такие запросы. Для любого фиксированного <tex>l</tex> методу нужно константное время на обнаруживаемый тандем, и никакой тандем не обнаруживается дважды, так как у всех обнаруживаемых тандемов длины <tex>2l</tex> стартовые точки различны. Поскольку сообщение о каждом повторе состоит из начальной точки и длины, то алгоритм никогда не сообщает о тандемном повторе дважды. Следовательно, время, расходуемое на вывод информации о тандемных повторах, пропорционально <tex>z_h</tex> — числу повторов, у которых первая копия покрывает позицию <tex>h</tex>.}}
Приведенный метод корректно решает подзадачу 3 для фиксированного <tex>h</tex> Это значит, что он находит все тандемные повторы, у которых первая копия покрывает позицию <tex>h</tex>.
Теперь покажем что сам Алгоритм правильный.
{{Теорема
|statement = Каждый тандемный повтор в <tex>S</tex> находится решением подзадач 1-4 и при этом только единожды. Время работы алгоритма равно <tex>O( n \log n + z)</tex>, где <tex>z</tex> — число всех тандемных повторов в <tex>S</tex>.
|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) + O( n)</tex> и <tex>T( n) = O( n \log n)</tex>, как и утверждалось.}}
