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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение|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) называется строка, которая одинаково читается как слева направо, так и справа налево.


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


Алгоритм

Идея

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

Псевдокод

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