Редактирование: Количество подпалиндромов в строке

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
#перенаправление [[Алгоритм Манакера]]
+
{{Шаблон:Задача
 +
|definition =
 +
Пусть дана строка <tex>s</tex>, требуется посчитать количество [[Основные_определения,_связанные_со_строками#palindrome | палиндромов]] в ней.
 +
}}
 +
 
 +
== Алгоритм ==
 +
=== Идея ===
 +
Рассмотрим сначала задачу поиска палиндромов нечетной длины. Центром строки нечетной длины назовем символ под индексом <tex>\left\lfloor \dfrac{|t|}{2}\right\rfloor</tex>. Для каждой позиции в строке <tex>s</tex> найдем длину наибольшего палиндрома с центром в этой позиции. Очевидно, что если строка <tex>t</tex> является палиндромом, то строка полученная вычеркиванием первого и последнего символа из <tex>t</tex> также является палиндромом, поэтому длину палиндрома можно искать [[Целочисленный_двоичный_поиск | бинарным поиском]]. Проверить совпадение левой и правой половины можно выполнить за <tex>O(1)</tex>, используя метод хеширования.
 +
 
 +
Для палиндромов четной длины алгоритм такой же. Центр строки четной длины {{---}} некий мнимый элемент между <tex>\dfrac{|t|}{2} - 1</tex> и <tex>\dfrac{|t|}{2}</tex>. Только требуется проверять вторую строку со сдвигом на единицу. Следует заметить, что мы не посчитаем никакой палиндром дважды из-за четности-нечетности длин палиндромов.
 +
 
 +
=== Псевдокод ===
 +
'''int''' binarySearch(s : '''string''', center, shift : '''int'''):
 +
    ''<font color=green>//shift = 0 при поиске палиндрома нечетной длины, иначе shift = 1</font>''
 +
    '''int''' l = -1, r = min(center, s.length - center + shift), m = 0
 +
    '''while''' r - l != 1
 +
        m = l + (r - l) / 2
 +
        ''<font color=green>//reversed_hash возвращает хэш развернутой строки s</font>''
 +
        '''if''' hash(s[center - m..center]) == reversed_hash(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
 +
 
 +
=== Время работы ===
 +
Изначальный подсчет хешей производится за <tex>O(|s|)</tex>. Каждая итерация будет выполняться за <tex>O(\log(|s|))</tex>, всего итераций {{---}} <tex>|s|</tex>. Итоговое время работы алгоритма <tex>O(|s|+|s|\cdot \log(|s|)) = O(|s|\cdot \log(|s|))</tex>.
 +
 
 +
=== Избавление от коллизий ===
 +
У хешей есть один недостаток {{---}} коллизии: можно подобрать входные данные так, что хеши разных строк будут совпадать. Абсолютно точно проверить две подстроки на совпадение можно с помощью [[Суффиксный массив | суффиксного массива]], но с дополнительной памятью <tex>O(|s|\cdot \log(|s|))</tex>. Для этого построим суффиксный массив для строки <tex>s + \# + reverse(s)</tex>, при этом сохраним промежуточные результаты классов эквивалентности <tex>c</tex>. Пусть нам требуется проверить на совпадение подстроки <tex>s[i..i + l]</tex> и <tex>s[j..j + l]</tex>. Разобьем каждую нашу строку на две пересекающиеся подстроки длиной <tex>2^k</tex>, где <tex>k = \lfloor \log{l} \rfloor</tex>. Тогда наши строки совпадают, если <tex>c[k][i] = c[k][j]</tex> и <tex>c[k][i + l - 2^k] = c[k][j + l - 2^k]</tex>.
 +
 
 +
Итоговая асимптотика алгоритма: предподсчет за построение суффиксного массива и <tex>O(\log(|s|))</tex> на запрос, если предподсчитать все <tex>k</tex>, то <tex>O(1)</tex>.
 +
 
 +
==См. также==
 +
*[[Суффиксный массив]]
 +
*[[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
 +
 
 +
==Источники информации==
 +
* [http://e-maxx.ru/algo/suffix_array#5 MAXimal :: algo :: Суффиксный массив]
 +
[[Категория:Алгоритмы и структуры данных]]
 +
[[Категория:Суффиксный массив]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)