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

Алгоритм Манакера (англ. Manacher's algorithm) — алгоритм с линейным временем работы, позволяющий получить в сжатом виде информацию обо всех палиндромных подстроках заданной строки. Предложен Гленном Манакером в 1975 году. Изначальной задачей, решаемой алгоритмом, был поиск наименьшего префикс-палиндрома заданной строки, однако получаемая в результате работы алгоритма структура позволяет решать и более общие задачи. Так, Манакером было продемонстрировано, что алгоритм позволяет проверить, может ли строка быть представлена в виде ${\displaystyle (\omega \omega ^{R})^{k}}$, где ${\displaystyle \omega }$ — некоторая строка, ${\displaystyle \omega ^{R}}$ — её обращение. В 1995 году Апостолико, Бреслауэр и Галил указали на то, что, по своему построению, алгоритм Манакера не только находит кратчайший префикс-палиндром, но также позволяет найти максимальные радиусы палиндромов для каждого возможного центра палиндромной подстроки.

Алгоритм Манакера
Предназначение	Поиск подпалиндромов
Структура данных	Строка
Худшее время	${\displaystyle O(n)}$
Затраты памяти	${\displaystyle O(n)}$

Постановка задачи

• Пусть ${\displaystyle \omega =\omega _{1}\omega _{2}\dots \omega _{n}}$ — некоторая строка. Её обращением называется строка ${\displaystyle \omega ^{R}=\omega _{n}\dots \omega _{2}\omega _{1}}$, составленная из тех же символов, но записанных в обратном порядке.
• Строка ${\displaystyle \omega }$ называется палиндромом если ${\displaystyle \omega =\omega ^{R}}$, то есть если она одинаково читается слева направо и справа налево.
• Палиндром ${\displaystyle \omega }$ называется чётным если имеет чётную длину и нечётным в противном случае. Любой чётный палиндром имеет вид ${\displaystyle \omega =vv^{R}}$, а нечётный имеет вид ${\displaystyle \omega =vav^{R}}$, где ${\displaystyle a}$ — произвольный символ.
• У строки ${\displaystyle \omega }$ есть чётный палиндром радиуса ${\displaystyle r}$ с центром в позиции ${\displaystyle k}$ если ${\displaystyle \omega _{k-i}=\omega _{k+i-1}}$ для ${\displaystyle i=1,\dots ,r}$. Соответственно, у строки есть нечётный палиндром радиуса ${\displaystyle r}$ с центром в ${\displaystyle k}$ если ${\displaystyle \omega _{k-i}=\omega _{k+i}}$ для ${\displaystyle i=1,\dots ,r}$.

• Радиус ${\displaystyle r}$ называется максимальным для позиции ${\displaystyle k}$ если у строки нет палиндрома с радиусом ${\displaystyle r+1}$ с центром в той же позиции.

Алгоритм Манакера позволяет за линейное время найти максимальные радиусы чётных и нечётных палиндромов в каждой позиции ${\displaystyle k=1,\dots ,n}$ строки ${\displaystyle \omega }$.

Реализация

Ниже приведена реализация алгоритма на 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]])

Функция manacher_odd возвращает массив Манакера для палиндромов нечётной длины, функция manacher возвращает пару из массивов Манакера для палиндромов нечётной и чётной длины соответственно, сводя вычисление массива для чётных длин к нечётному случаю путём добавления служебного символа #.

Литература

• Manacher G. K. A new linear-time “on-line” algorithm for finding the smallest initial palindrome of a string (англ.) // Journal of the ACM / D. J. Rosenkrantz — New York City: Association for Computing Machinery, 1975. — Vol. 22, Iss. 3. — P. 346—351. — ISSN 0004-5411; 1557-735X — doi:10.1145/321892.321896
• Apostolico A., Breslauer D., Galil Z. Parallel detection of all palindromes in a string (англ.) // Theoretical Computer Science — Elsevier BV, 1995. — Vol. 141, Iss. 1-2. — P. 163—173. — ISSN 0304-3975; 1879-2294 — doi:10.1016/0304-3975(94)00083-U