Изменения

Пусть дана строка <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>is</tex>, будем на каждом шаге увеличивать найдем длину наибольшего палиндрома с центром в этой позиции. Очевидно, что если строка <tex>it</tex> и убеждатьсяявляется палиндромом, что рассматриваемая то строка не перестала быть полученная вычеркиванием первого и последнего символа из <tex>t</tex> также является палиндромом, либо поэтому длину палиндрома можно искать [[Целочисленный_двоичный_поиск | бинарным поиском]]. Проверить совпадение левой и правой половины можно выполнить за <tex>O(1)</tex>, используя метод хеширования.  Для палиндромов чётной длины алгоритм такой же. Центр строки чётной длины {{---}} некий мнимый элемент между <tex>\dfrac{|t|}{2} - 1</tex> и <tex>\dfrac{|t|}{2}</tex>. Только требуется проверять вторую строку со сдвигом на единицу. Следует заметить, что мы не произошел выход посчитаем никакой палиндром дважды из-за границы массивачетности-нечетности длин палиндромов. === Псевдокод === '''int''' binarySearch(s : '''string''', center, shift : '''int'''): ''<font color=green>//shift = 0 при поиске палиндрома нечётной длины, иначе shift = 1</font>'' '''int''' l = -1, r = min(center, s.length - center + shift), m = 0 '''while''' r - l != 1 m = l + (r - l) / 2 ''<font color=green>//reversed_hash возвращает хэш развернутой строки s</font>'' '''if''' hash(s[center - m..center]) == reversed_hash(s[center + shift..center + shift + m]) l = m '''else''' r = m '''return''' r  '''int''' palindromesCount(s : '''string'''): '''int''' ans = 0 '''for''' i = 0 '''to''' s. Очевидноlength ans += binarySearch(s, i, 0) + binarySearch(s, i, что такой алгоритм 1) '''return''' ans === Время работы ===Изначальный подсчет хешей производится за <tex>O(|s|)</tex>. Каждая итерация будет работать выполняться за <tex>O(n\log(|s|))</tex>, всего итераций {{---}} <tex>|s|</tex>. Итоговое время работы алгоритма <tex>O(|s|+|s|\cdot \log(|s|)) = O(|s|\cdot \log(|s|))</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>.

===Псевдокод=== <font color=green>// Итоговая асимптотика алгоритма: предподсчет за построение суффиксного массива и <tex>O(\log(|s|))</tex> {{---}} исходная строкана запрос, если предподсчитать все </fonttex> k<font color=green>// <tex>d1, d2то </tex> {{---}} массивы для записи ответа</font> '''O(int[], int[]1)''' calculate('''string''' s): '''for''' i = 1 '''to''' n d1[i] = 1 '''while''' i - d1[i] > 0 '''and''' i + d1[i] <= n '''and''' s[i - d1[i]] == s[i + d1[i]] d1[i]++ d2[i] = 0 '''while''' i - d2[i] - 1 /tex> 0 '''and''' i + d2[i] <= n '''and''' s[i - d2[i] - 1] == s[i + d2[i]] d2[i]++ '''return''' (d1, d2).

Будем поддерживать границы самого правого из найденных палиндромов — <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>d_1[j] = k</tex>, мы можем утверждать, что и <tex>d1d_1[i] = d1k</tex>. Это объясняется тем, что палиндром симметричен относительно своей центральной позиции. Т.е. если имеем некоторый палиндром длины <tex>k</tex> с центром в позиции <tex>l \leqslant i \leqslant r</tex>, то в позиции <tex>j</tex>, симметричной <tex>i</tex> относительно отрезка <tex>[jl; 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>:

k = min(r - i, d<tex>d_1</tex>[r - i + l])

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

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

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

k = min(r - i + 1, d<tex>d_2</tex>[r - i + l + 1])

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

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

Т.к. значение <tex>r</tex> не может увеличиваться более <tex>n</tex> раз, то описанный выше алгоритм работает за линейное время<tex>O(n)</tex>.

* [[Z — -функция]]* [[Суффиксный массив]]* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]

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

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

[[Категория: Поиск подстроки в строкеОсновные определения. Простые комбинаторные свойства слов]]