Изменения
Нет описания правки
{{Шаблон:Задача
|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 = min(center, s.length- center + shift), m = 0
'''while''' r - l != 1
m = l + (r - l) / 2
ans += binarySearch(s, i, 0) + binarySearch(s, i, 1)
'''return''' 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>.
=== Избавление от коллизий ===
У хешей есть один недостаток {{---}} коллизии, у двух возможно подобрать входные данные так, что хеши разных строк хеши могут будут совпадать. Абсолютно точно проверить две подстроки на совпадение можно с помощью [[Суффиксный массив | суффиксного массива]], но с дополнительной памятью <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>.
Итоговая асимптотика алгоритма: предподсчет за построение суффиксного массива и <tex>O(\log(|s|))</tex> на запрос, если предподсчитать все <tex>k</tex>, то <tex>O(1)</tex>.
==См. также==
