Изменения

Пусть дана строка <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>\left\lfloor \dfrac{|t|}{2}\right\rfloor</tex>. Для каждой позиции в строке <tex>s</tex> найдем длину наибольшего палиндрома с центром в этой позиции. Очевидно, что если строка <tex>t</tex> является палиндромом, то строка полученная вычеркиванием первого и последнего символа из <tex>t</tex> также является палиндромом, поэтому длину палиндрома можно искать [[Целочисленный_двоичный_поиск | бинарным поиском]]. Проверить совпадение левой и правой половины можно выполнить за <tex>O(1)</tex>, используя метод хеширования.

Для палиндромов четной чётной длины алгоритм такой же. Центр строки четной чётной длины {{---}} некий мнимый элемент между <tex>\dfrac{|t|}{2} - 1</tex> и <tex>\dfrac{|t|}{2}</tex>. Только требуется проверять вторую строку со сдвигом на единицу. Следует заметить, что мы не посчитаем никакой палиндром дважды из-за четности-нечетности длин палиндромов.

''<font color=green>//shift = 0 при поиске палиндрома нечетной нечётной длины, иначе shift = 1</font>''

У хешей есть один недостаток {{---}} коллизии: можно подобрать входные данные так, что хеши разных строк будут совпадать. Абсолютно точно проверить две подстроки на совпадение можно с помощью [[Суффиксный массив | суффиксного массива]], но с дополнительной памятью <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>[l; r]</tex>. Итак, пусть мы хотим вычислить <tex>d1d_1[i]</tex> — т.е. длину наибольшего палиндрома с центром в позиции <tex>i</tex>. При этом все предыдущие значения в массиве <tex>d</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>d2d_2</tex> считается аналогичным образом, нужно лишь немного изменить индексы.

Приведем код, который вычисляет значения массива <tex>d1d_1</tex>:

d1<tex>d_1</tex>[i] = k

'''return''' d1<tex>d_1</tex>

Вычисление значений массива <tex>d2d_2</tex>:

d2<tex>d_2</tex>[i] = k

'''return''' d2<tex>d_2</tex>

*[http://e-maxx.ru/algo/palindromes_count MAXimal :: algo :: Нахождение всех подпалиндромов]

*[https://habrahabr.ru/post/276195/ Алгоритмы для поиска палиндромов — Хабр]* [http://e-maxx.ru/algo/suffix_array#5 MAXimal :: algo :: Суффиксный массив]