42
правки
Изменения
→Корректность
{{Лемма
|statement = Для фиксированного <tex>h</tex> время работы случая случай с перекрытием равно <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>.}}
Приведенный метод корректно решает случая случай с перекрытием для фиксированного <tex>h</tex> Это значит, что он находит все тандемные повторы, у которых первая копия покрывает позицию <tex>h</tex>.
Теперь покажем что сам Алгоритм правильный.
