Изменения

Рассмотрим сначала задачу поиска палиндромов нечетной длины. Центром строки нечетной длины назовем символ под индексом <tex>\lfloor \frac{|t|}{2}\rfloor</tex>. Для каждой позиции в строке <tex>s</tex> найдем длину наибольшего палиндрома с центром в этой позиции. Очевидно, что если строка <tex>t</tex> является палиндромом, то строка полученная вычеркиванием первого и последнего символа из <tex>t</tex> также является палиндромом, поэтому длину палиндрома можно искать [[Целочисленный_двоичный_поиск | бинарным поиском]]. Проверить совпадение левой и правой половины можно выполнить за <tex>O(1)</tex>, используя метод хеширования.

Для палиндромов четной длины алгоритм такой же, только следует . Центр строки четной длины {{---}} некий мнимый элемент между <tex>\frac{|t|}{2} - 1</tex> и <tex>\frac{|t|}{2}</tex>. Только требуется проверять вторую строку со сдвигом на единицу. Следует заметить, при этом что мы не посчитаем никакой палиндром дважды из-за четности-нечетности длин палиндромов.

''<font color=green>//reversed_hash возвращает хэш развернутой строки s</font>'' '''if''' hash(s[center - m..center]) == hash(reversereversed_hash(s[center + shift..center + shift + m]))

У хешей есть один недостаток {{---}} коллизии, возможно : можно подобрать входные данные так, что хеши разных строк будут совпадать. Абсолютно точно проверить две подстроки на совпадение можно с помощью [[Суффиксный массив | суффиксного массива]], но с дополнительной памятью <tex>O(|s|\cdot \log(|s|))</tex>. Для этого построим суффиксный массив для строки <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>.