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

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

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

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

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

Алгоритм Манакера позволяет за линейное время найти максимальные радиусы чётных и нечётных палиндромов в каждой позиции $k=1,\dots ,n$ строки $\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]])

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

Литература

• Шаблон:ВД-Источник
• Шаблон:ВД-Источник