Алгоритм Манакера — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Идея)
м (rollbackEdits.php mass rollback)
 
(не показаны 44 промежуточные версии 9 участников)
Строка 1: Строка 1:
 
{{Шаблон:Задача
 
{{Шаблон:Задача
 
|definition =  
 
|definition =  
Пусть дана строка <tex>s</tex>. Требуется найти <tex>d1[i]</tex> - длина наибольшего палиндрома нечетной длины с центром в позиции <tex>i</tex> и <tex>d2[i]</tex>- аналогично для палиндромов четной длины для всех <tex>i</tex> от 1 до <tex>|s|</tex>.
+
Пусть дана строка <tex>s</tex>. Требуется найти количество подстрок <tex>s</tex>, являющиеся палиндромами. Более формально, все такие пары <tex>(i, j)</tex>, что <tex>s[i \ldots j]</tex> — [[Основные_определения,_связанные_со_строками#palindrome | палиндром]].
 
}}
 
}}
 +
 +
==Уточнение постановки==
 +
Легко увидеть, что таких подстрок в худшем случае будет <tex>n^2</tex>. Значит, нужно найти компактный способ хранения информации о них. Пусть <tex>d_1[i]</tex> — количество палиндромов нечётной длины с центром в позиции <tex>i</tex>, а <tex>d_2[i]</tex> — аналогичная величина для палиндромов чётной длины. Далее научимся вычислять значения этих массивов.
  
 
== Наивный алгоритм ==
 
== Наивный алгоритм ==
===Идея===
+
=== Идея ===
Опишем сначала наивный алгоритм решения задачи. Чтобы посчитать ответ для позиции <tex>i</tex>, будем на каждом шаге увеличивать длину палиндрома с центром в <tex>i</tex> и убеждаться, что рассматриваемая строка не перестала быть палиндромом, либо не произошел выход за границы массива. Очевидно, что такой алгоритм будет работать за <tex>O(n^2)</tex>
+
Рассмотрим сначала задачу поиска палиндромов нечётной длины. Центром строки нечётной длины назовём символ под индексом <tex>\left\lfloor \dfrac{|t|}{2}\right\rfloor</tex>. Для каждой позиции в строке <tex>s</tex> найдем длину наибольшего палиндрома с центром в этой позиции. Очевидно, что если строка <tex>t</tex> является палиндромом, то строка полученная вычеркиванием первого и последнего символа из <tex>t</tex> также является палиндромом, поэтому длину палиндрома можно искать [[Целочисленный_двоичный_поиск | бинарным поиском]]. Проверить совпадение левой и правой половины можно выполнить за <tex>O(1)</tex>, используя метод хеширования.
===Псевдокод===
+
 
<font color=green>// <tex>s</tex> {{---}} исходная строка</font>
+
Для палиндромов чётной длины алгоритм такой же. Центр строки чётной длины {{---}} некий мнимый элемент между <tex>\dfrac{|t|}{2} - 1</tex> и <tex>\dfrac{|t|}{2}</tex>. Только требуется проверять вторую строку со сдвигом на единицу. Следует заметить, что мы не посчитаем никакой палиндром дважды из-за четности-нечетности длин палиндромов.
<font color=green>// <tex>d1, d2</tex> {{---}} массивы для записи ответа</font>
+
 
  '''for''' i = 1 '''to''' n
+
=== Псевдокод ===
    d1[i] = 1
+
'''int''' binarySearch(s : '''string''', center, shift : '''int'''):
    '''while''' i - d1[i] > 0 '''and''' i + d1[i] <= n '''and''' s[i - d1[i]] == s[i + d1[i]]
+
    ''<font color=green>//shift = 0 при поиске палиндрома нечётной длины, иначе shift = 1</font>''
      d1[i]++
+
    '''int''' l = -1, r = min(center, s.length - center + shift), m = 0
    d2[i] = 0
+
    '''while''' r - l != 1
    '''while''' i - d2[i] - 1 > 0 '''and''' i + d2[i] <= n '''and''' s[i - d2[i] - 1] == s[i + d2[i]]
+
        m = l + (r - l) / 2
      d2[i]++
+
        ''<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 \ldots i + l]</tex> и <tex>s[j \ldots 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>.
 +
 
 
==Алгоритм Манакера==
 
==Алгоритм Манакера==
 
===Идея===
 
===Идея===
 
Алгоритм, который будет описан далее, отличается от наивного тем, что использует значения, посчитанные ранее.  
 
Алгоритм, который будет описан далее, отличается от наивного тем, что использует значения, посчитанные ранее.  
Будем поддерживать границы самого правого из найденных палиндромов - <tex>[l; r]</tex>. Итак, пусть мы хотим вычислить <tex>d1[i]</tex> - т.е. длину наибольшего палиндрома с центром в позиции <tex>i</tex>. При этом все предыдущие значения в массиве <tex>d</tex> уже посчитаны. Возможны два случая:
+
Будем поддерживать границы самого правого из найденных палиндромов <tex>[l; r]</tex>. Итак, пусть мы хотим вычислить <tex>d_1[i]</tex> т.е. длину наибольшего палиндрома с центром в позиции <tex>i</tex>. При этом все предыдущие значения в массиве <tex>d</tex> уже посчитаны. Возможны два случая:
  
 
# <tex>i > r</tex>, т.е. текущая позиция не попадает в границы самого правого из найденных палиндромов. Тогда просто запустим наивный алгоритм для позиции <tex>i</tex>.
 
# <tex>i > r</tex>, т.е. текущая позиция не попадает в границы самого правого из найденных палиндромов. Тогда просто запустим наивный алгоритм для позиции <tex>i</tex>.
# <tex>i \leq r</tex>. Тогда попробуем воспользоваться значениями, посчитанным ранее. Отразим нашу текущую позицию внутри палиндрома <tex>[l;r] : j = (r - i) + l</tex>. Поскольку <tex>i</tex> и <tex>j</tex> - симметричные позиции, то мы можем утверждать, <tex>d1[i] = d1[j]</tex>. Однако надо не забыть про один граничный случай: что если <tex>i + d1[j] - 1</tex> выходит за границы самого правого палиндрома? Так как информации о том, что происходит за границами это палинлрома у нас нет, то необходимо ограничить значение <tex>d1[i]</tex> следующим образом: <tex>d1[i] = min(r - i, d1[j])</tex>. После этого запустим наивный алгоритм, который будет увеличивать значение <tex>d1[i]</tex>, пока это возможно.
+
# <tex>i \leqslant r</tex>. Тогда попробуем воспользоваться значениями, посчитанным ранее. Отразим нашу текущую позицию внутри палиндрома <tex>[l;r] : j = (r - i) + l</tex>. Поскольку <tex>i</tex> и <tex>j</tex> симметричные позиции, то если <tex>d_1[j] = k</tex>, мы можем утверждать, что и <tex>d_1[i] = k</tex>. Это объясняется тем, что палиндром симметричен относительно своей центральной позиции. Т.е. если имеем некоторый палиндром длины <tex>k</tex> с центром в позиции <tex>l \leqslant i \leqslant r</tex>, то в позиции <tex>j</tex>, симметричной <tex>i</tex> относительно отрезка <tex>[l; r]</tex> тоже может находиться палиндром длины <tex>k</tex>.  Это можно лучше понять, посмотрев на рисунок. Снизу фигурными скобками обозначены равные подстроки. Однако стоит не забыть про один граничный случай: что если <tex>i + d_1[j] - 1</tex> выходит за границы самого правого палиндрома? Так как информации о том, что происходит за границами этого палиндрома у нас нет (а значит мы не можем утверждать, что симметрия сохраняется), то необходимо ограничить значение <tex>d_1[i]</tex> следующим образом: <tex>d_1[i] = \min(r - i, d_1[j])</tex>. После этого запустим наивный алгоритм, который будет увеличивать значение <tex>d_1[i]</tex>, пока это возможно.
  
После каждого шага важно не забывать обновлять значения <tex>[l;r]</tex>
+
После каждого шага важно не забывать обновлять значения <tex>[l;r]</tex>.
  
Заметим, что массив <tex>d2</tex> считается аналогичным образом, нужно лишь немного изменить индексы.
+
Заметим, что массив <tex>d_2</tex> считается аналогичным образом, нужно лишь немного изменить индексы.
  
 
[[Файл:Манакер.png]]
 
[[Файл:Манакер.png]]
  
 
===Псевдокод===
 
===Псевдокод===
Приведем код, который вычисляет значения массива <tex>d1</tex>:
+
Приведем код, который вычисляет значения массива <tex>d_1</tex>:
  
 
  <font color=green>// <tex>s</tex> {{---}} исходная строка</font>
 
  <font color=green>// <tex>s</tex> {{---}} исходная строка</font>
  '''int''' l = 0
+
  '''int[]''' calculate1('''string''' s):
'''int''' r = -1
+
  '''int''' l = 0
'''for''' i = 1 '''to''' n
+
  '''int''' r = -1
  '''int''' k = 0
+
  '''for''' i = 1 '''to''' n
  '''if''' i <= r
+
    '''int''' k = 0
      k = min(r - i, d[r - i + l])
+
    '''if''' i <= r
  '''while''' i + k + 1 <= n '''and''' i - k - 1 > 0 '''and''' s[i + k + 1] == s[i - k - 1]
+
        k = min(r - i, <tex>d_1</tex>[r - i + l])
      k++
+
    '''while''' i + k + 1 <= n '''and''' i - k - 1 > 0 '''and''' s[i + k + 1] == s[i - k - 1]
    d1[i] = k
+
        k++
    '''if''' i + k > r
+
      <tex>d_1</tex>[i] = k
      l = i - k
+
      '''if''' i + k > r
      r = i + k
+
        l = i - k
 +
        r = i + k
 +
  '''return''' <tex>d_1</tex>
  
Вычисление значений массива <tex>d2</tex>:
+
Вычисление значений массива <tex>d_2</tex>:
 
  <font color=green>// <tex>s</tex> {{---}} исходная строка</font>
 
  <font color=green>// <tex>s</tex> {{---}} исходная строка</font>
  '''int''' l = 0
+
  '''int[]''' calculate2('''string''' s):
'''int''' r = -1
+
  '''int''' l = 0
'''for''' i = 1 '''to''' n
+
  '''int''' r = -1
  '''int''' k = 0
+
  '''for''' i = 1 '''to''' n
  '''if''' i <= r
+
    '''int''' k = 0
      k = min(r - i + 1, d[r - i + l + 1])
+
    '''if''' i <= r
  '''while''' i + k <= n '''and''' i - k - 1 > 0 '''and''' s[i + k] == s[i - k - 1]
+
        k = min(r - i + 1, <tex>d_2</tex>[r - i + l + 1])
      k++
+
    '''while''' i + k <= n '''and''' i - k - 1 > 0 '''and''' s[i + k] == s[i - k - 1]
    d2[i] = k
+
        k++
    '''if''' i + k - 1 > r
+
      <tex>d_2</tex>[i] = k
      l = i - k
+
      '''if''' i + k - 1 > r
      r = i + k - 1
+
        l = i - k
 +
        r = i + k - 1
 +
  '''return''' <tex>d_2</tex>
  
 
===Оценка сложности===
 
===Оценка сложности===
Внешний цикл в приведенном алгоритме выполняется ровно <tex>n</tex> раз, где <tex>n</tex> - длина строки. Попытаемся понять, сколько раз будет выполнен внутренний цикл, ответственный за наивный подсчет значений. Заметим, что каждая итерация вложенного цикла приводит к увеличению <tex>r</tex> на 1. Действительно, возможны следующие случаи:
+
Внешний цикл в приведенном алгоритме выполняется ровно <tex>n</tex> раз, где <tex>n</tex> длина строки. Попытаемся понять, сколько раз будет выполнен внутренний цикл, ответственный за наивный подсчет значений. Заметим, что каждая итерация вложенного цикла приводит к увеличению <tex>r</tex> на <tex>1</tex>. Действительно, возможны следующие случаи:
 +
 
 +
# <tex>i > r</tex>, т.е. сразу будет запущен наивный алгоритм и каждая его итерация будет увеличивать значение <tex>r</tex> хотя бы на <tex>1</tex>.
 +
# <tex>i \leqslant r</tex>. Здесь опять два случая:
 +
## <tex>i + d[j] - 1 \leqslant r</tex>, но тогда, очевидно, ни одной итерации вложенного цикла выполнено не будет.
 +
## <tex>i + d[j] - 1 > r</tex>,  тогда каждая итерация вложенного цикла приведет к увеличению <tex>r</tex> хотя бы на <tex>1</tex>.
 +
 
 +
Т.к. значение <tex>r</tex> не может увеличиваться более <tex>n</tex> раз, то описанный выше алгоритм работает за время <tex>O(n)</tex>.
 +
 
 +
== См. также ==
 +
* [[Префикс-функция]]
 +
* [[Z-функция]]
 +
* [[Суффиксный массив]]
 +
* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
  
# <tex>i > r</tex>, т.е. сразу будет запущен наивный алгоритм и каждая его итерация будет увеличивать значение <tex>r</tex> хотя бы на 1
+
== Источники информации ==
# <tex>i \leq r</tex>. Здесь опять два случая:
+
* [http://e-maxx.ru/algo/palindromes_count MAXimal :: algo :: Нахождение всех подпалиндромов]
## <tex>i + d[j] - 1 \leq r</tex>, но тогда, очевидно, ни одной итерации вложенного цикла выполнено не будет
+
* [[wikipedia:ru:Поиск_длиннейшей_подстроки-палиндрома| Википедия — Поиск длиннейшей подстроки-палиндрома]]
## <tex>i + d[j] - 1 > r</tex>,  тогда каждая итерация вложенного цикла приведет к увеличению <tex>r</tex> хотя бы на 1.
+
* [https://habrahabr.ru/post/276195/ Алгоритмы для поиска палиндромов — Хабр]
 +
* [http://e-maxx.ru/algo/suffix_array#5 MAXimal :: algo :: Суффиксный массив]
  
Т.к. значение <tex>r</tex> не может увеличиваться более <tex>n</tex> раз, то описанный выше алгоритм работает за линейное время.
+
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Основные определения. Простые комбинаторные свойства слов]]

Текущая версия на 19:29, 4 сентября 2022

Задача:
Пусть дана строка [math]s[/math]. Требуется найти количество подстрок [math]s[/math], являющиеся палиндромами. Более формально, все такие пары [math](i, j)[/math], что [math]s[i \ldots j][/math] палиндром.


Уточнение постановки

Легко увидеть, что таких подстрок в худшем случае будет [math]n^2[/math]. Значит, нужно найти компактный способ хранения информации о них. Пусть [math]d_1[i][/math] — количество палиндромов нечётной длины с центром в позиции [math]i[/math], а [math]d_2[i][/math] — аналогичная величина для палиндромов чётной длины. Далее научимся вычислять значения этих массивов.

Наивный алгоритм

Идея

Рассмотрим сначала задачу поиска палиндромов нечётной длины. Центром строки нечётной длины назовём символ под индексом [math]\left\lfloor \dfrac{|t|}{2}\right\rfloor[/math]. Для каждой позиции в строке [math]s[/math] найдем длину наибольшего палиндрома с центром в этой позиции. Очевидно, что если строка [math]t[/math] является палиндромом, то строка полученная вычеркиванием первого и последнего символа из [math]t[/math] также является палиндромом, поэтому длину палиндрома можно искать бинарным поиском. Проверить совпадение левой и правой половины можно выполнить за [math]O(1)[/math], используя метод хеширования.

Для палиндромов чётной длины алгоритм такой же. Центр строки чётной длины — некий мнимый элемент между [math]\dfrac{|t|}{2} - 1[/math] и [math]\dfrac{|t|}{2}[/math]. Только требуется проверять вторую строку со сдвигом на единицу. Следует заметить, что мы не посчитаем никакой палиндром дважды из-за четности-нечетности длин палиндромов.

Псевдокод

int binarySearch(s : string, center, shift : int):
    //shift = 0 при поиске палиндрома нечётной длины, иначе shift = 1
    int l = -1, r = min(center, s.length - center + shift), m = 0
    while r - l != 1
        m = l + (r - l) / 2
        //reversed_hash возвращает хэш развернутой строки s
        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

Время работы

Изначальный подсчет хешей производится за [math]O(|s|)[/math]. Каждая итерация будет выполняться за [math]O(\log(|s|))[/math], всего итераций — [math]|s|[/math]. Итоговое время работы алгоритма [math]O(|s|+|s|\cdot \log(|s|)) = O(|s|\cdot \log(|s|))[/math].

Избавление от коллизий

У хешей есть один недостаток — коллизии: можно подобрать входные данные так, что хеши разных строк будут совпадать. Абсолютно точно проверить две подстроки на совпадение можно с помощью суффиксного массива, но с дополнительной памятью [math]O(|s|\cdot \log(|s|))[/math]. Для этого построим суффиксный массив для строки [math]s + \# + reverse(s)[/math], при этом сохраним промежуточные результаты классов эквивалентности [math]c[/math]. Пусть нам требуется проверить на совпадение подстроки [math]s[i \ldots i + l][/math] и [math]s[j \ldots j + l][/math]. Разобьем каждую нашу строку на две пересекающиеся подстроки длиной [math]2^k[/math], где [math]k = \lfloor \log{l} \rfloor[/math]. Тогда наши строки совпадают, если [math]c[k][i] = c[k][j][/math] и [math]c[k][i + l - 2^k] = c[k][j + l - 2^k][/math].

Итоговая асимптотика алгоритма: предподсчет за построение суффиксного массива и [math]O(\log(|s|))[/math] на запрос, если предподсчитать все [math]k[/math], то [math]O(1)[/math].

Алгоритм Манакера

Идея

Алгоритм, который будет описан далее, отличается от наивного тем, что использует значения, посчитанные ранее. Будем поддерживать границы самого правого из найденных палиндромов — [math][l; r][/math]. Итак, пусть мы хотим вычислить [math]d_1[i][/math] — т.е. длину наибольшего палиндрома с центром в позиции [math]i[/math]. При этом все предыдущие значения в массиве [math]d[/math] уже посчитаны. Возможны два случая:

  1. [math]i \gt r[/math], т.е. текущая позиция не попадает в границы самого правого из найденных палиндромов. Тогда просто запустим наивный алгоритм для позиции [math]i[/math].
  2. [math]i \leqslant r[/math]. Тогда попробуем воспользоваться значениями, посчитанным ранее. Отразим нашу текущую позицию внутри палиндрома [math][l;r] : j = (r - i) + l[/math]. Поскольку [math]i[/math] и [math]j[/math] — симметричные позиции, то если [math]d_1[j] = k[/math], мы можем утверждать, что и [math]d_1[i] = k[/math]. Это объясняется тем, что палиндром симметричен относительно своей центральной позиции. Т.е. если имеем некоторый палиндром длины [math]k[/math] с центром в позиции [math]l \leqslant i \leqslant r[/math], то в позиции [math]j[/math], симметричной [math]i[/math] относительно отрезка [math][l; r][/math] тоже может находиться палиндром длины [math]k[/math]. Это можно лучше понять, посмотрев на рисунок. Снизу фигурными скобками обозначены равные подстроки. Однако стоит не забыть про один граничный случай: что если [math]i + d_1[j] - 1[/math] выходит за границы самого правого палиндрома? Так как информации о том, что происходит за границами этого палиндрома у нас нет (а значит мы не можем утверждать, что симметрия сохраняется), то необходимо ограничить значение [math]d_1[i][/math] следующим образом: [math]d_1[i] = \min(r - i, d_1[j])[/math]. После этого запустим наивный алгоритм, который будет увеличивать значение [math]d_1[i][/math], пока это возможно.

После каждого шага важно не забывать обновлять значения [math][l;r][/math].

Заметим, что массив [math]d_2[/math] считается аналогичным образом, нужно лишь немного изменить индексы.

Манакер.png

Псевдокод

Приведем код, который вычисляет значения массива [math]d_1[/math]:

// [math]s[/math] — исходная строка
int[] calculate1(string s):
  int l = 0
  int r = -1
  for i = 1 to n
    int k = 0
    if i <= r
       k = min(r - i, [math]d_1[/math][r - i + l])
    while i + k + 1 <= n and i - k - 1 > 0 and s[i + k + 1] == s[i - k - 1]
       k++
     [math]d_1[/math][i] = k
     if i + k > r
       l = i - k
       r = i + k
  return [math]d_1[/math]

Вычисление значений массива [math]d_2[/math]:

// [math]s[/math] — исходная строка
int[] calculate2(string s):
  int l = 0
  int r = -1
  for i = 1 to n
    int k = 0
    if i <= r
       k = min(r - i + 1, [math]d_2[/math][r - i + l + 1])
    while i + k <= n and i - k - 1 > 0 and s[i + k] == s[i - k - 1]
       k++
     [math]d_2[/math][i] = k
     if i + k - 1 > r
       l = i - k
       r = i + k - 1
  return [math]d_2[/math]

Оценка сложности

Внешний цикл в приведенном алгоритме выполняется ровно [math]n[/math] раз, где [math]n[/math] — длина строки. Попытаемся понять, сколько раз будет выполнен внутренний цикл, ответственный за наивный подсчет значений. Заметим, что каждая итерация вложенного цикла приводит к увеличению [math]r[/math] на [math]1[/math]. Действительно, возможны следующие случаи:

  1. [math]i \gt r[/math], т.е. сразу будет запущен наивный алгоритм и каждая его итерация будет увеличивать значение [math]r[/math] хотя бы на [math]1[/math].
  2. [math]i \leqslant r[/math]. Здесь опять два случая:
    1. [math]i + d[j] - 1 \leqslant r[/math], но тогда, очевидно, ни одной итерации вложенного цикла выполнено не будет.
    2. [math]i + d[j] - 1 \gt r[/math], тогда каждая итерация вложенного цикла приведет к увеличению [math]r[/math] хотя бы на [math]1[/math].

Т.к. значение [math]r[/math] не может увеличиваться более [math]n[/math] раз, то описанный выше алгоритм работает за время [math]O(n)[/math].

См. также

Источники информации