Тандемные повторы

Постановка задачи

Назовем тандемным повтором такую подстроку четной длины $S[i..j]$, что

$$S[i \ldots \frac{i + j}{2}] = S[\frac{i + j}{2} + 1 \ldots j]$$

Наша задача --- найти самую длинную подстроку в строке S, которая является тандемным повтором.

Идея

Давайте воспользуемся методом Разделяй и властвуй. Будем делить строку пополам, искать ответ для левой и правой половины, после чего склеивать ответы обратно, находя число тандемных повторов, которые лежат и в левой, и в правой половине.

Теперь хочется за $O(n)$ найти самый длинный тандемный повтор, который пересекается центром. Давайте предположим, что центр разбивает правую половину тандема, а другой случай рассмотрим симметрично.

Переберем место, парное тому, где произошло разделение. А именно, если размер искомого тандемного повтора был $2d$, то переберем точку, находящуюся на расстоянии $d$ слева от центра. Назовем эту точку $j$, а самую левую точку тандемного повтора назовем $i$. Тогда у нас появилось разбиение на $S[i \ldots j]$ и $S[j+1 \ldots i + d - 1]$. Заметим, что парные им блоки были слева и справа от разделителя разделяй-и-властвуй. То есть теперь нам надо проверить равенство каких-то подстрок $S$ и подстрок, которые границей примыкают к разделителю.

Z-функция

Чтобы оптимизировать последний шаг, воспользуемся z-функцией. А именно, чтобы сравнить левые части, заранее посчитаем z-функцию для левой половины строки, и будем смотреть, сколько символов совпало. Для сравнения правых частей тандема склеим строки $S[\frac{n}{2} \ldots n]$ и $S[0 \ldots \frac{n}{2}-1]$. Насчитав z-функцию на них, мы получим нужное расстояние для позиции $j$. Останется только проверить, что сумма двух длин не меньше $d$. При нахождении максимального тандемного повтора это будет критерием на обновление $d_{max}$. Общая асимптотика $O(n \log n)$