Изменения

Пусть дана строка <tex>s</tex>. Требуется найти количество подстрок <tex>d1[i]s</tex> - длина наибольшего палиндрома нечетной длины с центром в позиции , являющиеся палиндромами. Более формально, все такие пары <tex>(i, j)</tex> и , что <tex>d2s[i\ldots j]</tex>- аналогично для палиндромов четной длины для всех <tex>i</tex> от 1 до <tex>— [[Основные_определения,_связанные_со_строками#palindrome |s|</tex>палиндром]].

===Идея===Опишем Рассмотрим сначала наивный алгоритм решения задачизадачу поиска палиндромов нечётной длины. Центром строки нечётной длины назовём символ под индексом <tex>\left\lfloor \dfrac{|t|}{2}\right\rfloor</tex>. Чтобы посчитать ответ для Для каждой позиции в строке <tex>is</tex>, будем на каждом шаге увеличивать найдем длину наибольшего палиндрома с центром в этой позиции. Очевидно, что если строка <tex>it</tex> и убеждатьсяявляется палиндромом, что рассматриваемая то строка не перестала быть полученная вычеркиванием первого и последнего символа из <tex>t</tex> также является палиндромом, либо не произошел выход за границы массивапоэтому длину палиндрома можно искать [[Целочисленный_двоичный_поиск | бинарным поиском]]. Очевидно, что такой алгоритм будет работать Проверить совпадение левой и правой половины можно выполнить за <tex>O(n^21)</tex>, используя метод хеширования. ===Псевдокод=== <font color=green>// <tex>s</tex> Для палиндромов чётной длины алгоритм такой же. Центр строки чётной длины {{---}} исходная строканекий мнимый элемент между </fonttex> \dfrac{|t|}{2} - 1<font color=green>// <tex>d1, d2и </tex> \dfrac{|t|}{---2}} массивы для записи ответа</fonttex>. Только требуется проверять вторую строку со сдвигом на единицу. Следует заметить, что мы не посчитаем никакой палиндром дважды из-за четности-нечетности длин палиндромов. === Псевдокод === '''int'''forbinarySearch(s : '''string''' i = 1 , center, shift : '''toint''' n): d1[i] ''<font color=green>//shift = 0 при поиске палиндрома нечётной длины, иначе shift = 1</font>'' '''whileint''' i l = -1, r = min(center, s.length - d1[i] > center + shift), m = 0 '''andwhile''' i r - l != 1 m = l + d1[i] (r - l) / 2 ''<font color= n green>//reversed_hash возвращает хэш развернутой строки s</font>'' 'and''if' '' hash(s[i center - d1[i]m..center] ) == reversed_hash(s[i center + shift..center + shift + d1[i]m]) l = m '''else''' r = m '''return''' r  d1[i]++ '''int''' palindromesCount(s : '''string'''): d2[i] '''int''' ans = 0 '''whilefor''' i - d2[i] - 1 > = 0 '''andto''' s.length ans += binarySearch(s, i , 0) + d2[binarySearch(s, i] <= n , 1) '''andreturn''' ans === Время работы ===Изначальный подсчет хешей производится за <tex>O(|s|)</tex>. Каждая итерация будет выполняться за <tex>O(\log(|s|))</tex>, всего итераций {{---}} <tex>|s|</tex>. Итоговое время работы алгоритма <tex>O(|s|+|s|\cdot \log(|s|)) = O(|s|\cdot \log(|s|))</tex>. === Избавление от коллизий ===У хешей есть один недостаток {{---}} коллизии: можно подобрать входные данные так, что хеши разных строк будут совпадать. Абсолютно точно проверить две подстроки на совпадение можно с помощью [i - d2[iСуффиксный массив | суффиксного массива] - 1] == , но с дополнительной памятью <tex>O(|s|\cdot \log(|s|))</tex>. Для этого построим суффиксный массив для строки <tex>s + \# + reverse(s)</tex>, при этом сохраним промежуточные результаты классов эквивалентности <tex>c</tex>. Пусть нам требуется проверить на совпадение подстроки <tex>s[i \ldots i + d2l]</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] d2[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 \leq 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>[l;r]</tex>.

Заметим, что массив <tex>d2d_2</tex> считается аналогичным образом, нужно лишь немного изменить индексы.

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

'''int[]''' calculate1('''string''' s): '''int''' l = 0 '''int''' r = -1 '''for''' i = 1 '''to''' n '''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++ d1 <tex>d_1</tex>[i] = k '''if''' i + k > r l = i - k r = i + k '''return''' <tex>d_1</tex>

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

'''int[]''' calculate2('''string''' s): '''int''' l = 0 '''int''' r = -1 '''for''' i = 1 '''to''' n '''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++ d2 <tex>d_2</tex>[i] = k '''if''' i + k - 1 > r l = i - k r = i + k - 1 '''return''' <tex>d_2</tex>

Внешний цикл в приведенном алгоритме выполняется ровно <tex>n</tex> раз, где <tex>n</tex> - — длина строки. Попытаемся понять, сколько раз будет выполнен внутренний цикл, ответственный за наивный подсчет значений. Заметим, что каждая итерация вложенного цикла приводит к увеличению <tex>r</tex> на <tex>1</tex>. Действительно, возможны следующие случаи: # <tex>i > r</tex>, т.е. сразу будет запущен наивный алгоритм и каждая его итерация будет увеличивать значение <tex>r</tex> хотя бы на <tex>1</tex>.# <tex>i \leqslant r</tex>. Здесь опять два случая:## <tex>i + d[j] - 1 \leqslant r</tex>, но тогда, очевидно, ни одной итерации вложенного цикла выполнено не будет.## <tex>i + d[j] - 1 > r</tex>, тогда каждая итерация вложенного цикла приведет к увеличению <tex>r</tex> хотя бы на <tex>1</tex>. Т.к. значение <tex>r</tex> не может увеличиваться более <tex>n</tex> раз, то описанный выше алгоритм работает за время <tex>O(n)</tex>. == См. также ==* [[Префикс-функция]]* [[Z-функция]]* [[Суффиксный массив]]* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]

# <tex>i > r<== Источники информации ==* [http://tex>, т.еe-maxx. сразу будет запущен наивный алгоритм и каждая его итерация будет увеличивать значение <tex>r<ru/tex> хотя бы на 1# <tex>i \leq r<algo/tex>. Здесь опять два случаяpalindromes_count MAXimal :: algo ::Нахождение всех подпалиндромов]## <tex>i + d* [[jwikipedia:ru:Поиск_длиннейшей_подстроки-палиндрома| Википедия — Поиск длиннейшей подстроки-палиндрома] - 1 \leq r<]* [https://habrahabr.ru/post/276195/tex>, но тогда, очевидно, ни одной итерации вложенного цикла выполнено не будетАлгоритмы для поиска палиндромов — Хабр]## <tex>i + d* [j] http://e- 1 > r<maxx.ru/tex>, тогда каждая итерация вложенного цикла приведет к увеличению <tex>r<algo/tex> хотя бы на 1.suffix_array#5 MAXimal :: algo :: Суффиксный массив]

Т.к. значение <tex>r</tex> не может увеличиваться более <tex>n</tex> раз, то описанный выше алгоритм работает за линейное время[[Категория: Алгоритмы и структуры данных]][[Категория: Основные определения.Простые комбинаторные свойства слов]]