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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 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
+
    '''while''' r - l != 1
          m = l + (r - l) / 2
+
        m = l + (r - l) / 2
          '''if''' hash(s[center - m..center]) == hash(reverse(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'''
              r = m
+
            r = m
 
     '''return''' r
 
     '''return''' r
  
 
  '''int''' palindromesCount(s : '''string'''):
 
  '''int''' palindromesCount(s : '''string'''):
    '''int''' n = s.length
 
 
     '''int''' ans = 0
 
     '''int''' ans = 0
     '''for''' i = 0 '''to''' n
+
     '''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) называется строка, которая одинаково читается как слева направо, так и справа налево.


Задача:
Пусть дана строка [math]s[/math], требуется посчитать количество подпалиндромов в ней за [math]O(|s|\cdot\log{|s|)}[/math].


Алгоритм

Идея

Для каждой позиции в строке [math]s[/math] найдем длину наибольшего палиндрома с центром в этой позиции. Длину палиндрома будем искать бинарным поиском. Для сохранения асимптотики проверку совпадения левой и правой половины требуется выполнить за [math]O(1)[/math]. Для этого можно воспользоваться методом хеширования.

Псевдокод

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