Викиконспекты - Вклад участника [ru]

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

2016-03-10T19:52:41Z

217.66.156.233:

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

== Наивный алгоритм ==
===Идея===
Опишем сначала наивный алгоритм решения задачи. Чтобы посчитать ответ для позиции <tex>i</tex>, будем на каждом шаге увеличивать длину палиндрома с центром в <tex>i</tex> и убеждаться, что рассматриваемая строка не перестала быть палиндромом, либо не произошел выход за границы массива. Очевидно, что такой алгоритм будет работать за <tex>O(n^2)</tex>
===Псевдокод===
// <tex>s</tex> {{---}} исходная строка
// <tex>d1, d2</tex> {{---}} массивы для записи ответа
'''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]++
==Алгоритм Манакера==
===Идея===
Алгоритм, который будет описан далее, отличается от наивного тем, что использует значения, посчитанные ранее.
Будем поддерживать границы самого правого из найденных палиндромов - <tex>[l; r]</tex>. Итак, пусть мы хотим вычислить <tex>d1[i]</tex> - т.е. длину наибольшего палиндрома с центром в позиции <tex>i</tex>. При этом все предыдущие значения в массиве <tex>d</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>[l;r]</tex>

Заметим, что массив <tex>d2</tex> считается аналогичным образом, нужно лишь немного изменить индексы.

===Псевдокод===
Приведем код, который вычисляет значения массива <tex>d1</tex>:

// <tex>s</tex> {{---}} исходная строка
'''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++
d1[i] = k
'''if''' i + k > r
l = i - k
r = i + k

Вычисление значений массива <tex>d2</tex>:
// <tex>s</tex> {{---}} исходная строка
'''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++
d2[i] = k
'''if''' i + k - 1 > r
l = i - k
r = i + k - 1

===Оценка сложности===
Внешний цикл в приведенном алгоритме выполняется ровно <tex>n</tex> раз, где <tex>n</tex> - длина строки. Попытаемся понять, сколько раз будет выполнен внутренний цикл, ответственный за наивный подсчет значений. Заметим, что каждая итерация вложенного цикла приводит к увеличению <tex>r</tex> на 1. Действительно, возможны следующие случаи:

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

Т.к. значение <tex>r</tex> не может увеличиваться более <tex>n</tex> раз, то описанный выше алгоритм работает за линейное время.

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

2016-03-10T19:39:07Z

217.66.156.233:

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

== Наивный алгоритм ==
===Идея===
Опишем сначала наивный алгоритм решения задачи. Чтобы посчитать ответ для позиции <tex>i</tex>, будем на каждом шаге увеличивать длину палиндрома с центром в <tex>i</tex> и убеждаться, что рассматриваемая строка не перестала быть палиндромом, либо не произошел выход за границы массива. Очевидно, что такой алгоритм будет работать за <tex>O(n^2)</tex>
===Псевдокод===
// <tex>s</tex> {{---}} исходная строка
// <tex>d1, d2</tex> {{---}} массивы для записи ответа
'''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]++
==Алгоритм Манакера==
===Идея===
Алгоритм, который будет описан далее, отличается от наивного тем, что использует значения, посчитанные ранее.
Будем поддерживать границы самого правого из найденных палиндромов - <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])</tex>. После этого запустим наивный алгоритм, который будет увеличивать значение <tex>d1[i]</tex>, пока это возможно.

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

Заметим, что массив <tex>d2</tex> считается аналогичным образом, нужно лишь немного изменить индексы.

===Псевдокод===
Приведем код, который вычисляет значения массива <tex>d1</tex>:

// <tex>s</tex> {{---}} исходная строка
'''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++
d1[i] = k
'''if''' i + k > r
l = i - k
r = i + k

Вычисление значений массива <tex>d2</tex>:
// <tex>s</tex> {{---}} исходная строка
'''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++
d2[i] = k
'''if''' i + k - 1 > r
l = i - k
r = i + k - 1

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

2016-03-10T19:08:35Z

217.66.156.233:

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

== Наивный алгоритм ==
===Идея===
Опишем сначала наивный алгоритм решения задачи. Чтобы посчитать ответ для позиции <tex>i</tex>, будем на каждом шаге увеличивать длину палиндрома с центром в <tex>i</tex> и убеждаться, что рассматриваемая строка не перестала быть палиндромом, либо не произошел выход за границы массива. Очевидно, что такой алгоритм будет работать за <tex>O(n^2)</tex>
===Псевдокод===
// <tex>s</tex> {{---}} исходная строка
// <tex>d1, d2</tex> {{---}} массивы для записи ответа
'''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]++
==Алгоритм Манакера==
===Идея===
Алгоритм, который будет описан далее, отличается от наивного тем, что использует значения, посчитанные ранее.
Будем поддерживать границы самого правого из найденных палиндромов - <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]). После этого запустим наивный алгоритм, который будет увеличивать значение <tex>d1[i]</tex>, пока это возможно.

Заметим, что массив <tex>d2</tex> считается аналогичным образом, нужно лишь немного изменить индексы.

===Псевдокод===
Приведем код, который вычисляет значения массивов <tex>d1</tex> и <tex>d2</tex>

// <tex>s</tex> {{---}} исходная строка
// <tex>d1, d2</tex> {{---}} массивы для записи ответа
'''int''' l = 0
'''int''' r = -1
'''for''' i = 1 '''to''' n
'''int''' k = 1
'''if''' i <= r
k = k + min(r - i, d[r - i + l])
'''while''' i + k <= n '''and''' i - k > 0 '''and''' s[i + k] == s[i - k]
k++
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]++

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

2016-03-10T18:55:24Z

217.66.156.233: