Изменения

== Алгоритм ==

* Найти все тандемные повторы, содержащиеся целиком в первой половине <tex>S</tex>(до позиции <tex>h</tex> включительно).

|[[Файл: tandem1.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>.]]

|}

Мы хотим найти все тандемные повторы, у которых первая копия покрывает позицию <tex>h</tex> (но не обязательно начинается в ней). Идея алгоритма заключается в следующем. Для любого фиксированного <tex>l</tex> можно за константное время проверить, существует ли такой тандемный повтор длины <tex>2l</tex>, у которого первая копия покрывает позицию <tex>h</tex>. Применение этого теста ко всем допустимым значениям <tex>l</tex> означает, что за время <tex>O( n)</tex> мы можем найти все длины таких тандемных повторов. Более того, для каждой такой длины мы можем перечислить начальные точки этих тандемных повторов за время, пропорциональное их числу. Ниже описано, как проверить

число <tex>l</tex>.