Тандемные повторы: различия между версиями
KiKoS (обсуждение | вклад) (Новая страница: «==Постановка задачи== Назовем `тандемным повтором` такую подстроку четной длины $S[i..j]$, чт...») |
KiKoS (обсуждение | вклад) м |
||
Строка 1: | Строка 1: | ||
==Постановка задачи== | ==Постановка задачи== | ||
− | Назовем `тандемным повтором` такую подстроку четной длины $S[i..j]$, что | + | Назовем ``тандемным повтором`` такую подстроку четной длины $S[i..j]$, что |
− | $$S[i | + | $$S[i \ldots \frac{i + j}{2}] = S[\frac{i + j}{2} + 1 \ldots j]$$ |
Наша задача --- найти самую длинную подстроку в строке S, которая является тандемным повтором. | Наша задача --- найти самую длинную подстроку в строке S, которая является тандемным повтором. | ||
Строка 13: | Строка 13: | ||
Теперь хочется за $O(n)$ найти самый длинный тандемный повтор, который пересекается центром. Давайте предположим, что центр разбивает правую половину тандема, а другой случай рассмотрим симметрично. | Теперь хочется за $O(n)$ найти самый длинный тандемный повтор, который пересекается центром. Давайте предположим, что центр разбивает правую половину тандема, а другой случай рассмотрим симметрично. | ||
− | Переберем место, парное тому, где произошло разделение. А именно, если размер искомого тандемного повтора был $2d$, то переберем точку, находящуюся на расстоянии $d$ слева от центра. Назовем эту точку $j$, а самую левую точку тандемного повтора назовем $i$. Тогда у нас появилось разбиение на $S[i | + | Переберем место, парное тому, где произошло разделение. А именно, если размер искомого тандемного повтора был $2d$, то переберем точку, находящуюся на расстоянии $d$ слева от центра. Назовем эту точку $j$, а самую левую точку тандемного повтора назовем $i$. Тогда у нас появилось разбиение на $S[i \ldots j]$ и $S[j+1 \ldots i + d - 1]$. Заметим, что парные им блоки были слева и справа от разделителя разделяй-и-властвуй. То есть теперь нам надо проверить равенство каких-то подстрок $S$ и подстрок, которые границей примыкают к разделителю. |
==Z-функция== | ==Z-функция== | ||
− | Чтобы оптимизировать последний шаг, воспользуемся [[z-функция|z-функцией]]. А именно, чтобы сравнить левые части, заранее посчитаем z-функцию для левой половины строки, и будем смотреть, сколько символов совпало. Для сравнения правых частей тандема склеим строки $S[\frac{n}{2} | + | Чтобы оптимизировать последний шаг, воспользуемся [[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)$ |
Версия 18:07, 19 ноября 2020
Постановка задачи
Назовем ``тандемным повтором`` такую подстроку четной длины $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)$