42
правки
Изменения
→Алгоритм для задачи 3
# Вычислить наибольшее общее продолжение (в прямом направлении) из позиций <tex>h</tex> и <tex>q</tex>. Пусть <tex>l_1</tex> — длина этого продолжения.
# Вычислить наибольшее общее продолжение (в обратном направлении) из позиций <tex>h - 1</tex> и <tex>q - 1</tex>. Пусть <tex>l_2</tex> — длина этого продолжения.
# Тандемный повтор длины <tex>2l</tex>, первая копия которого покрывает позицию <tex>h</tex>, существует в том и только том случае, если <tex>l_1 + l_2 \geqslant l</tex> и обе длины <tex>l_1</tex> и <tex>l_2</tex> положительны. Более того, если такой тандемный повтор длины <tex>2l</tex> существует, то он может начинаться в любой позиции от <tex>\max ( h - l_2 , \ h - l + 1)</tex> до <tex>\min ( h + l_1 - l, \ h)</tex> включительно. Вторая копия повтора начинается в <tex>l</tex> позициях вправо. Вывести каждую из этих начальных позиций вместе с длиной <tex>2l</tex>.
=== Корректность ===
