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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 17: Строка 17:
 
     '''while''' i - d2[i] - 1 > 0 '''and''' i + d2[i] <= n '''and''' s[i - d2[i] - 1] == s[i + d2[i]]
 
     '''while''' i - d2[i] - 1 > 0 '''and''' i + d2[i] <= n '''and''' s[i - d2[i] - 1] == s[i + d2[i]]
 
       d2[i]++
 
       d2[i]++
 +
==Алгоритм Манакера==
 +
===Идея===
 +
Алгоритм, который будет описан далее, отличается от наивного тем, что использует значения, посчитанные ранее.
 +
Будем поддерживать границы самого правого из найденных палиндромов - <tex>[l; r]</tex>. Итак, пусть мы хотим вычислить <tex>d1[i]</tex> - т.е. длину наибольшего палиндрома с центром в позиции <tex>i</tex>. При этом все предыдущие значения в массиве <tex>d</tex> уже посчитаны. Возможны два случая:
 +
 +
1. <tex>i > r</tex>, т.е. текущая позиция не попадает в границы самого правого из найденных палиндромов. Тогда просто запустим наивный алгоритм для позиции <tex>i</tex>.
 +
 +
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]).

Версия 21:55, 10 марта 2016

Задача:
Пусть дана строка [math]s[/math]. Требуется найти [math]d1[i][/math] - длина наибольшего палиндрома нечетной длины с центром в позиции [math]i[/math] и [math]d2[i][/math]- аналогично для палиндромов четной длины для всех [math]i[/math] от 1 до [math]|s|[/math].


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

Идея

Опишем сначала наивный алгоритм решения задачи. Чтобы посчитать ответ для позиции [math]i[/math], будем на каждом шаге увеличивать длину палиндрома с центром в [math]i[/math] и убеждаться, что рассматриваемая строка не перестала быть палиндромом, либо не произошел выход за границы массива. Очевидно, что такой алгоритм будет работать за [math]O(n^2)[/math]

Псевдокод

// [math]s[/math] — исходная строка
// [math]d1, d2[/math] — массивы для записи ответа
 for i = 1 to n
   d1[i] = 1
   while i - d1[i] > 0 and i + d1[i] <= n and s[i - d1[i]] == s[i + d1[i]]
     d1[i]++
   d2[i] = 0
   while i - d2[i] - 1 > 0 and i + d2[i] <= n and s[i - d2[i] - 1] == s[i + d2[i]]
     d2[i]++

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

Идея

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

1. [math]i \gt r[/math], т.е. текущая позиция не попадает в границы самого правого из найденных палиндромов. Тогда просто запустим наивный алгоритм для позиции [math]i[/math].

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