{{Шаблон:Задача|definition = Пусть дана строка <tex>s</tex>, требуется посчитать количество #перенаправление [[Основные_определения,_связанные_со_строками#palindrome | палиндромов]] в ней за <tex>O(|s|\cdot\log{|s|)}</tex> c помощью хешей.}}== Алгоритм ===== Идея ===Рассмотрим сначала задачу поиска палиндромов нечетной длины. Для каждой позиции в строке <tex>s</tex> найдем длину наибольшего палиндрома с центром в этой позиции. Очевидно, что если строка <tex>t</tex> является палиндромом, то строка полученная вычеркиванием первого и последнего символа из <tex>t</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=== Избавление от коллизий ===У хешей есть один недостаток {{---}} коллизии, у двух разных строк хеши могут совпадать. Абсолютно точно проверить две подстроки на совпадение можно с помощью [[Суффиксный массив | суффиксного массива]]. Для этого построим суффиксный массив для строки <tex>s + \# + reverse(s)</tex>, при этом сохраним промежуточные результаты классов эквивалентности <tex>c</tex>. Пусть нам требуется проверить на совпадение подстроки <tex>s[i..i + l]</tex> и <tex>s[j..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>.==См. также==*[[Суффиксный массив]]*[[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]==Источники информации==* [http://e-maxx.ru/algo/suffix_array#5 MAXimal :: algo :: Суффиксный массив][[Категория:Алгоритмы и структуры данных]][[Категория:Суффиксный массивМанакера]]
