Количество подпалиндромов в строке — различия между версиями
(Новая страница: «{{Определение|definition='''Палиндромом''' (англ. <i>Palindrome</i>) называется строка, которая одинаков...») |
|||
Строка 14: | Строка 14: | ||
'''while''' r - l != 1 | '''while''' r - l != 1 | ||
m = l + (r - l) / 2 | m = l + (r - l) / 2 | ||
− | '''if''' hash(s[center - m..center]) == hash(s[center + shift..center + shift + m]) | + | '''if''' hash(s[center - m..center]) == hash(reverse(s[center + shift..center + shift + m])) |
l = m | l = m | ||
'''else''' | '''else''' |
Версия 18:46, 19 марта 2016
Определение: |
Палиндромом (англ. Palindrome) называется строка, которая одинаково читается как слева направо, так и справа налево. |
Задача: |
Пусть дана строка | , требуется посчитать количество подпалиндромов в ней за .
Алгоритм
Идея
Для каждой позиции в строке
найдем длину наибольшего палиндрома с центром в этой позиции. Длину палиндрома будем искать бинарным поиском. Для сохранения асимптотики проверку совпадения левой и правой половины требуется выполнить за . Для этого можно воспользоваться методом хеширования.Псевдокод
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(reverse(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