Алгоритм Манакера () — алгоритм с линейным временем работы, позволяющий получить в сжатом виде информацию обо всех палиндромных подстроках заданной строки. Предложен Гленном Манакером в 1975 году. Изначальной задачей, решаемой алгоритмом, был поиск наименьшего префикс-палиндрома заданной строки, однако получаемая в результате работы алгоритма структура позволяет решать и более общие задачи. Так, Манакером было продемонстрировано, что алгоритм позволяет проверить, может ли строка быть представлена в виде , где — некоторая строка, — её обращение. В 1995 году Апостолико, Бреслауэр и Галил указали на то, что, по своему построению, алгоритм Манакера не только находит кратчайший префикс-палиндром, но также позволяет найти максимальные радиусы палиндромов для каждого возможного центра палиндромной подстроки.
Постановка задачи Пусть — некоторая строка. Её обращением называется строка , составленная из тех же символов, но записанных в обратном порядке. Строка называется палиндромом если , то есть если она одинаково читается слева направо и справа налево. Палиндром называется чётным если имеет чётную длину и нечётным в противном случае. Любой чётный палиндром имеет вид , а нечётный имеет вид , где — произвольный символ. У строки есть чётный палиндром радиуса с центром в позиции если для . Соответственно, у строки есть нечётный палиндром радиуса с центром в если для .
Радиус называется максимальным для позиции если у строки нет палиндрома с радиусом с центром в той же позиции.
Алгоритм Манакера позволяет за линейное время найти максимальные радиусы чётных и нечётных палиндромов в каждой позиции строки .
Реализация Ниже приведена реализация алгоритма на Python.def manacher_odd(s): s = '$' + s + '^' n = len(s) res = * 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]])Функция возвращает массив Манакера для палиндромов нечётной длины, функция возвращает пару из массивов Манакера для палиндромов нечётной и чётной длины соответственно, сводя вычисление массива для чётных длин к нечётному случаю путём добавления служебного символа .
Литература
Категория:Строковые алгоритмы