Изменения
добавилась картинка
== Определения ==
{{Определение
|definition='''Тандемные ряды.''' (англ. ''tandem array'') {{---}} Подстрока <tex>\alpha</tex>, содержащаяся в строке <tex> \mathrm{S} </tex>, называется тандемным рядом строки <tex>\beta</tex> (называемой основой), если а состоит из более чем одной последовательной копии <tex>\beta</tex>.
Например, <tex>axabaybb</tex> — тандемный повтор точности 2.
== Алгоритм ==
Метод нахождения всех тандемных повторой за время <tex>O(n \log n + z)</tex>, где <tex>z</tex> — полное число тандемных повторов в <tex>\mathrm{S}</tex>. Метод разработали Ландау и Шмидт.
Рещение Ландау-Шмидта — это рекурсивный алгоритм типа "разделяй и властвуй", который основан на возможности вычислять запросы о наибольшем общем продолжении за константное время. Пусть <tex>h = [n/2]</tex>. В укрупненном масштабе метод Ландау-Шмидта делит задачу нахождения всех тандемных повторов на четыре подзадачи:
число <tex>l</tex>.
begin
end.
[[Файл:tandem.png|Рис. 1. Схематичная иллюстрация к алгоритму для задачи 3.|800px]]
///////////////картинка
Любая позиция между <tex>A</tex> и <tex>B</tex> включительно может быть начальной точкой тандемного повтора длины <tex>2l</tex>. Как указывается в шаге 4, длины <tex>l_1</tex> и <tex>l_2</tex> обе положительны, поэтому подынтервал этих начальных точек определяет тандемные повторы, в которых первая копия покрывает <tex>h</tex>.
== Теорема ==
{{Лемма
|statement = Приведенный метод корректно решает подзадачу 3 для фиксированного <tex>h</tex> Это значит, что он находит все тандемные повторы, у которых первая копия покрывает позицию <tex>h</tex>. Для фиксированного <tex>h</tex> его время работы равно <tex>O(n/2) + z_h</tex>, где <tex>z_h</tex> — число таких тандемных повторов.
