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

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

Версия 21:23, 21 марта 2017

Задача:
Пусть дана строка [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, d[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, d[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].

См. также

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