Изменения

===Идея===Опишем Рассмотрим сначала наивный алгоритм решения задачизадачу поиска палиндромов нечетной длины. Чтобы посчитать ответ для Центром строки нечетной длины назовем символ под индексом <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[], int[])''' calculatebinarySearch(s : '''string''' s), center, shift : '''forint'''): '' i <font color=green>//shift = 0 при поиске палиндрома нечетной длины, иначе shift = 1 </font>'' '''toint''' n d1[i] l = -1, r = min(center, s.length - center + shift), m = 0 '''while''' i r - l != 1 m = l + (r - d1[i] > 0 l) / 2 ''<font color=green>//reversed_hash возвращает хэш развернутой строки s</font>'and''' i + d1[i] <= n '''andif''' 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..i + d2l]</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] d2[i+ l - 2^k] = c[k][j ++l - 2^k]</tex>.   '''return''' Итоговая асимптотика алгоритма: предподсчет за построение суффиксного массива и <tex>O(\log(d1|s|))</tex> на запрос, d2если предподсчитать все <tex>k</tex>, то <tex>O(1)</tex>.