Количество подпалиндромов в строке — различия между версиями
| Строка 11: | Строка 11: | ||
=== Псевдокод === | === Псевдокод === | ||
'''int''' binarySearch(s : '''string''', center, shift : '''int'''): | '''int''' binarySearch(s : '''string''', center, shift : '''int'''): | ||
| + | ''<font color=green>shift = 0 при поиске палиндрома нечетной длины, иначе shift = 1</font>'' | ||
'''int''' l = -1, r = s.length, m = 0 | '''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 | '''return''' r | ||
'''int''' palindromesCount(s : '''string'''): | '''int''' palindromesCount(s : '''string'''): | ||
| − | |||
'''int''' ans = 0 | '''int''' ans = 0 | ||
| − | '''for''' i = 0 '''to''' | + | '''for''' i = 0 '''to''' s.length |
ans += binarySearch(s, i, 0) + binarySearch(s, i, 1) | ans += binarySearch(s, i, 0) + binarySearch(s, i, 1) | ||
'''return''' ans | '''return''' ans | ||
Версия 19:35, 19 марта 2016
| Определение: |
| Палиндромом (англ. Palindrome) называется строка, которая одинаково читается как слева направо, так и справа налево. |
| Задача: |
| Пусть дана строка , требуется посчитать количество подпалиндромов в ней за . |
Алгоритм
Идея
Для каждой позиции в строке найдем длину наибольшего палиндрома с центром в этой позиции. Длину палиндрома будем искать бинарным поиском. Для сохранения асимптотики проверку совпадения левой и правой половины требуется выполнить за . Для этого можно воспользоваться методом хеширования.
Псевдокод
int binarySearch(s : string, center, shift : int):
shift = 0 при поиске палиндрома нечетной длины, иначе shift = 1
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
