1632
правки
Изменения
м
d1<tex>d_1</tex>[i] = k
d2<tex>d_2</tex>[i] = k
rollbackEdits.php mass rollback
{{Шаблон:Задача
|definition =
Пусть дана строка <tex>s</tex>. Требуется найти количество подстрок <tex>s</tex>, являющиеся палиндромами. Более формально, все такие пары <tex>(i, j)</tex>, что <tex>s[i..\ldots j]</tex> — [[Основные_определения,_связанные_со_строками#palindrome | палиндром]].
}}
==Уточнение постановки==
Легко увидеть, что таких подстрок в худшем случае будет <tex>n^2</tex>. Значит, нужно найти компактный способ хранения информации о них. Пусть <tex>d1d_1[i]</tex> — количество палиндромов нечётной длины с центром в позиции <tex>i</tex>, а <tex>d2d_2[i]</tex> — аналогичная величина для палиндромов чётной длины. Далее научимся вычислять значения этих массивов.
== Наивный алгоритм ==
=== Избавление от коллизий ===
У хешей есть один недостаток {{---}} коллизии: можно подобрать входные данные так, что хеши разных строк будут совпадать. Абсолютно точно проверить две подстроки на совпадение можно с помощью [[Суффиксный массив | суффиксного массива]], но с дополнительной памятью <tex>O(|s|\cdot \log(|s|))</tex>. Для этого построим суффиксный массив для строки <tex>s + \# + reverse(s)</tex>, при этом сохраним промежуточные результаты классов эквивалентности <tex>c</tex>. Пусть нам требуется проверить на совпадение подстроки <tex>s[i..\ldots i + l]</tex> и <tex>s[j..\ldots j + l]</tex>. Разобьем каждую нашу строку на две пересекающиеся подстроки длиной <tex>2^k</tex>, где <tex>k = \lfloor \log{l} \rfloor</tex>. Тогда наши строки совпадают, если <tex>c[k][i] = c[k][j]</tex> и <tex>c[k][i + l - 2^k] = c[k][j + l - 2^k]</tex>.
Итоговая асимптотика алгоритма: предподсчет за построение суффиксного массива и <tex>O(\log(|s|))</tex> на запрос, если предподсчитать все <tex>k</tex>, то <tex>O(1)</tex>.
===Идея===
Алгоритм, который будет описан далее, отличается от наивного тем, что использует значения, посчитанные ранее.
Будем поддерживать границы самого правого из найденных палиндромов — <tex>[l; r]</tex>. Итак, пусть мы хотим вычислить <tex>d1d_1[i]</tex> — т.е. длину наибольшего палиндрома с центром в позиции <tex>i</tex>. При этом все предыдущие значения в массиве <tex>d</tex> уже посчитаны. Возможны два случая:
# <tex>i > r</tex>, т.е. текущая позиция не попадает в границы самого правого из найденных палиндромов. Тогда просто запустим наивный алгоритм для позиции <tex>i</tex>.
# <tex>i \leqslant r</tex>. Тогда попробуем воспользоваться значениями, посчитанным ранее. Отразим нашу текущую позицию внутри палиндрома <tex>[l;r] : j = (r - i) + l</tex>. Поскольку <tex>i</tex> и <tex>j</tex> — симметричные позиции, то если <tex>d1d_1[j] = k</tex>, мы можем утверждать, что и <tex>d1d_1[i] = k</tex>. Это объясняется тем, что палиндром симметричен относительно своей центральной позиции. Т.е. если имеем некоторый палиндром длины <tex>k</tex> с центром в позиции <tex>l \leqslant i \leqslant r</tex>, то в позиции <tex>j</tex>, симметричной <tex>i</tex> относительно отрезка <tex>[l; r]</tex> тоже может находиться палиндром длины <tex>k</tex>. Это можно лучше понять, посмотрев на рисунок. Снизу фигурными скобками обозначены равные подстроки. Однако стоит не забыть про один граничный случай: что если <tex>i + d1d_1[j] - 1</tex> выходит за границы самого правого палиндрома? Так как информации о том, что происходит за границами это палинлрома этого палиндрома у нас нет (а значит мы не можем утверждать, что симметрия сохраняется), то необходимо ограничить значение <tex>d1d_1[i]</tex> следующим образом: <tex>d1d_1[i] = \min(r - i, d1d_1[j])</tex>. После этого запустим наивный алгоритм, который будет увеличивать значение <tex>d1d_1[i]</tex>, пока это возможно.
После каждого шага важно не забывать обновлять значения <tex>[l;r]</tex>.
Заметим, что массив <tex>d2d_2</tex> считается аналогичным образом, нужно лишь немного изменить индексы.
[[Файл:Манакер.png]]
===Псевдокод===
Приведем код, который вычисляет значения массива <tex>d1d_1</tex>:
<font color=green>// <tex>s</tex> {{---}} исходная строка</font>
'''int''' k = 0
'''if''' i <= r
k = min(r - i, d<tex>d_1</tex>[r - i + l])
'''while''' i + k + 1 <= n '''and''' i - k - 1 > 0 '''and''' s[i + k + 1] == s[i - k - 1]
k++
'''if''' i + k > r
l = i - k
r = i + k
'''return''' d1<tex>d_1</tex>
Вычисление значений массива <tex>d2d_2</tex>:
<font color=green>// <tex>s</tex> {{---}} исходная строка</font>
'''int[]''' calculate2('''string''' s):
'''int''' k = 0
'''if''' i <= r
k = min(r - i + 1, d<tex>d_2</tex>[r - i + l + 1])
'''while''' i + k <= n '''and''' i - k - 1 > 0 '''and''' s[i + k] == s[i - k - 1]
k++
'''if''' i + k - 1 > r
l = i - k
r = i + k - 1
'''return''' d2<tex>d_2</tex>
===Оценка сложности===
