Русская Википедия:Алгоритм Манакера
Шаблон:Алгоритм Алгоритм Манакера (Шаблон:Lang-en) — алгоритм с линейным временем работы, позволяющий получить в сжатом виде информацию обо всех палиндромных подстроках заданной строки. Предложен Гленном Манакером в 1975 году. Изначальной задачей, решаемой алгоритмом, был поиск наименьшего префикс-палиндрома заданной строки, однако получаемая в результате работы алгоритма структура позволяет решать и более общие задачи. Так, Манакером было продемонстрировано, что алгоритм позволяет проверить, может ли строка быть представлена в виде <math>(\omega \omega^R)^k</math>, где <math>\omega</math> — некоторая строка, <math>\omega^R</math> — её обращение. В 1995 году Апостолико, Бреслауэр и Галил указали на то, что, по своему построению, алгоритм Манакера не только находит кратчайший префикс-палиндром, но также позволяет найти максимальные радиусы палиндромов для каждого возможного центра палиндромной подстроки.
Постановка задачи
- Пусть <math>\omega = \omega_1 \omega_2 \dots \omega_n</math> — некоторая строка. Её обращением называется строка <math>\omega^R = \omega_n \dots \omega_2 \omega_1</math>, составленная из тех же символов, но записанных в обратном порядке.
- Строка <math>\omega</math> называется палиндромом если <math>\omega = \omega^R</math>, то есть если она одинаково читается слева направо и справа налево.
- Палиндром <math>\omega</math> называется чётным если имеет чётную длину и нечётным в противном случае. Любой чётный палиндром имеет вид <math>\omega = vv^R</math>, а нечётный имеет вид <math>\omega = vav^R</math>, где <math>a</math> — произвольный символ.
- У строки <math>\omega</math> есть чётный палиндром радиуса <math>r</math> с центром в позиции <math>k</math> если <math>\omega_{k-i}=\omega_{k+i-1}</math> для <math>i=1,\dots,r</math>. Соответственно, у строки есть нечётный палиндром радиуса <math>r</math> с центром в <math>k</math> если <math>\omega_{k-i}=\omega_{k+i}</math> для <math>i=1,\dots,r</math>.
- Радиус <math>r</math> называется максимальным для позиции <math>k</math> если у строки нет палиндрома с радиусом <math>r+1</math> с центром в той же позиции.
Алгоритм Манакера позволяет за линейное время найти максимальные радиусы чётных и нечётных палиндромов в каждой позиции <math>k=1,\dots,n</math> строки <math>\omega</math>.
Реализация
Ниже приведена реализация алгоритма на Python.
def manacher_odd(s):
s = '$' + s + '^'
n = len(s)
res = [0] * n
l = 0
r = 0
for i in range(1, n - 1):
res[i] = max(0, min(r - i, res[l + (r - i)]))
while s[i - res[i]] == s[i + res[i]]:
res[i] += 1
if i + res[i] > r:
l = i - res[i]
r = i + res[i]
return res[1:-1]
def manacher(s):
res = manacher_odd('#' + '#'.join(s) + '#')[1:-1]
return ([x // 2 for x in res[::2]], [x // 2 for x in res[1::2]])
Функция Шаблон:Codevar возвращает массив Манакера для палиндромов нечётной длины, функция Шаблон:Codevar возвращает пару из массивов Манакера для палиндромов нечётной и чётной длины соответственно, сводя вычисление массива для чётных длин к нечётному случаю путём добавления служебного символа Шаблон:Code.
Литература
