{{Определение|definition='''Палиндромом''' (англ. <i>Palindrome</i>) называется строка, которая одинаково читается как слева направо, так и справа налево.}}{{Шаблон:Задача|definition = Пусть дана строка <tex>s</tex>, требуется посчитать количество подпалиндромов в ней за <tex>O(|s|\cdot\log{|s|)}</tex>.}}== Алгоритм ===== Идея ===Для каждой позиции в строке <tex>s</tex> найдем длину наибольшего палиндрома с центром в этой позиции. Длину палиндрома будем искать бинарным поиском. Для сохранения асимптотики проверку совпадения левой и правой половины требуется выполнить за <tex>O(1)</tex>. Для этого можно воспользоваться методом хеширования.=== Псевдокод === '''int''' binarySearch(s : '''string''', center, shift : '''int'''): ''<font color=green>//shift = 0 при поиске палиндрома нечетной длины, иначе shift = 1</font>'' '''int''' l = -1, r = s.length, m = 0 '''while''' r - l != 1 m = l + (r - l) / 2 '''if''' hash(s#перенаправление [center - m..center]) == hash(reverse(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==См. также==*[[Поиск наибольшей общей подстроки двух строк с использованием хеширования]][[Категория:Алгоритмы и структуры данных]][[Категория:Суффиксный массивАлгоритм Манакера]]
