Материал из Викиконспекты
|
|
| (не показано 9 промежуточных версий 4 участников) |
| Строка 1: |
Строка 1: |
| − | {{Определение|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'''):
| |
| − | ''<font color=green>shift = 0 при поиске палиндрома нечетной длины, иначе shift = 1</font>''
| |
| − | '''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
| |
Текущая версия на 23:00, 18 апреля 2016
