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

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

Текущая версия на 23:00, 18 апреля 2016

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