Количество подпалиндромов в строке — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Перенаправление на Алгоритм Манакера)
 
(не показано 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

Перенаправление на: