Изменения

Метод нахождения всех тандемных повторой за время <tex>O( n \log n + z)</tex>, где <tex>z</tex> — число всех тандемных повторов в <tex>S</tex>. Метод разработали Ландау и Шмидт.Рещение Ландау-Шмидта — это рекурсивный алгоритм типа "разделяй и властвуй", который основан на возможности вычислять запросы о наибольшем общем продолжении за константное время. Пусть <tex>h = [(n/2])</tex>. В укрупненном масштабе метод Ландау-Шмидта делит задачу нахождения всех тандемных повторов на четыре подзадачи:

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

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

# Вычислить наибольшее общее продолжение ( в прямом направлении) из позиций <tex>h</tex> и <tex>q</tex>. Пусть <tex>l_1</tex> — длина этого продолжения.# Вычислить наибольшее общее продолжение ( в обратном направлении) из позиций <tex>h - 1</tex> и <tex>q - 1</tex>. Пусть <tex>l_2</tex> — длина этого продолжения.