Изменения
Новая страница: «{{Определение|definition='''Палиндромом''' (англ. <i>Palindrome</i>) называется строка, которая одинаков...»
{{Определение|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'''):
'''int''' l = -1, r = s.length, m = 0
'''while''' r - l != 1
m = l + (r - l) / 2
'''if''' hash(s[center - m..center]) == hash(s[center + shift..center + shift + m])
l = m
'''else'''
r = m
'''return''' r
'''int''' palindromesCount(s : '''string'''):
'''int''' n = s.length
'''int''' ans = 0
'''for''' i = 0 '''to''' n
ans += binarySearch(s, i, 0) + binarySearch(s, i, 1)
'''return''' ans
{{Шаблон:Задача
|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'''):
'''int''' l = -1, r = s.length, m = 0
'''while''' r - l != 1
m = l + (r - l) / 2
'''if''' hash(s[center - m..center]) == hash(s[center + shift..center + shift + m])
l = m
'''else'''
r = m
'''return''' r
'''int''' palindromesCount(s : '''string'''):
'''int''' n = s.length
'''int''' ans = 0
'''for''' i = 0 '''to''' n
ans += binarySearch(s, i, 0) + binarySearch(s, i, 1)
'''return''' ans
