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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 48 промежуточных версий 10 участников)
Строка 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>\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 \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>i</tex>, будем на каждом шаге увеличивать длину палиндрома с центром в <tex>i</tex> и убеждаться, что рассматриваемая строка не перестала быть палиндромом, либо не произошел выход за границы массива. Очевидно, что такой алгоритм будет работать за <tex>O(n^2)</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 \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>d_2</tex> считается аналогичным образом, нужно лишь немного изменить индексы.
 +
 
 +
[[Файл:Манакер.png]]
 +
 
 
===Псевдокод===
 
===Псевдокод===
 +
Приведем код, который вычисляет значения массива <tex>d_1</tex>:
 +
 +
<font color=green>// <tex>s</tex> {{---}} исходная строка</font>
 +
'''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, <tex>d_1</tex>[r - i + l])
 +
    '''while''' i + k + 1 <= n '''and''' i - k - 1 > 0 '''and''' s[i + k + 1] == s[i - k - 1]
 +
        k++
 +
      <tex>d_1</tex>[i] = k
 +
      '''if''' i + k > r
 +
        l = i - k
 +
        r = i + k
 +
  '''return''' <tex>d_1</tex>
 +
 +
Вычисление значений массива <tex>d_2</tex>:
 
  <font color=green>// <tex>s</tex> {{---}} исходная строка</font>
 
  <font color=green>// <tex>s</tex> {{---}} исходная строка</font>
  <font color=green>// <tex>d1, d2</tex> {{---}} массивы для записи ответа</font>
+
  '''int[]''' calculate2('''string''' s):
  '''for''' i = 1 '''to''' n
+
  '''int''' l = 0
    d1[i] = 1
+
  '''int''' r = -1
    '''while''' i - d1[i] > 0 '''and''' i + d1[i] <= n '''and''' s[i - d1[i]] == s[i + d1[i]]
+
  '''for''' i = 1 '''to''' n
      d1[i]++
+
    '''int''' k = 0
    d2[i] = 0
+
    '''if''' i <= r
    '''while''' i - d2[i] - 1 > 0 '''and''' i + d2[i] <= n '''and''' s[i - d2[i] - 1] == s[i + d2[i]]
+
        k = min(r - i + 1, <tex>d_2</tex>[r - i + l + 1])
      d2[i]++
+
    '''while''' i + k <= n '''and''' i - k - 1 > 0 '''and''' s[i + k] == s[i - k - 1]
==Алгоритм Манакера==
+
        k++
===Идея===
+
      <tex>d_2</tex>[i] = k
Алгоритм, который будет описан далее, отличается от наивного тем, что использует значения, посчитанные ранее.
+
      '''if''' i + k - 1 > r
Будем поддерживать границы самого правого из найденных палиндромов - <tex>[l; r]</tex>. Итак, пусть мы хотим вычислить <tex>d1[i]</tex> - т.е. длину наибольшего палиндрома с центром в позиции <tex>i</tex>. При этом все предыдущие значения в массиве <tex>d</tex> уже посчитаны. Возможны два случая:
+
        l = i - k
 +
        r = i + k - 1
 +
  '''return''' <tex>d_2</tex>
 +
 
 +
===Оценка сложности===
 +
Внешний цикл в приведенном алгоритме выполняется ровно <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-функция]]
 +
* [[Суффиксный массив]]
 +
* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
  
1. <tex>i > r</tex>, т.е. текущая позиция не попадает в границы самого правого из найденных палиндромов. Тогда просто запустим наивный алгоритм для позиции <tex>i</tex>.
+
== Источники информации ==
 +
* [http://e-maxx.ru/algo/palindromes_count MAXimal :: algo :: Нахождение всех подпалиндромов]
 +
* [[wikipedia:ru:Поиск_длиннейшей_подстроки-палиндрома| Википедия — Поиск длиннейшей подстроки-палиндрома]]
 +
* [https://habrahabr.ru/post/276195/ Алгоритмы для поиска палиндромов — Хабр]
 +
* [http://e-maxx.ru/algo/suffix_array#5 MAXimal :: algo :: Суффиксный массив]
  
2. <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]).
+
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Основные определения. Простые комбинаторные свойства слов]]

Текущая версия на 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].

См. также

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