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

Задача:

Пусть дана строка [math]s[/math]. Требуется найти количество подстрок [math]s[/math], являющиеся палиндромами. Более формально, все такие пары [math](i, j)[/math], что [math]s[i..j][/math] — палиндром.

Уточнение постановки

Легко увидеть, что таких подстрок в худшем случае будет [math]n^2[/math]. Значит, нужно найти компактный способ хранения информации о них. Пусть [math]d1[i][/math] — количество палиндромов нечетной длины с центром в позиции [math]i[/math], а [math]d2[i][/math] — аналогичная величина для палиндромов четной длины. Далее научимся вычислять значения этих массивов.

Наивный алгоритм

Идея

Рассмотрим сначала задачу поиска палиндромов нечетной длины. Центром строки нечетной длины назовем символ под индексом [math]\left\lfloor \dfrac{|t|}{2}\right\rfloor[/math]. Для каждой позиции в строке [math]s[/math] найдем длину наибольшего палиндрома с центром в этой позиции. Очевидно, что если строка [math]t[/math] является палиндромом, то строка полученная вычеркиванием первого и последнего символа из [math]t[/math] также является палиндромом, поэтому длину палиндрома можно искать бинарным поиском. Проверить совпадение левой и правой половины можно выполнить за [math]O(1)[/math], используя метод хеширования.

Для палиндромов четной длины алгоритм такой же. Центр строки четной длины — некий мнимый элемент между [math]\dfrac{|t|}{2} - 1[/math] и [math]\dfrac{|t|}{2}[/math]. Только требуется проверять вторую строку со сдвигом на единицу. Следует заметить, что мы не посчитаем никакой палиндром дважды из-за четности-нечетности длин палиндромов.

Псевдокод

int binarySearch(s : string, center, shift : int):
    //shift = 0 при поиске палиндрома нечетной длины, иначе shift = 1
    int l = -1, r = min(center, s.length - center + shift), m = 0
    while r - l != 1
        m = l + (r - l) / 2
        //reversed_hash возвращает хэш развернутой строки s
        if hash(s[center - m..center]) == reversed_hash(s[center + shift..center + shift + m])
            l = m
        else
            r = m
    return r

int palindromesCount(s : string):
    int ans = 0
    for i = 0 to s.length
        ans += binarySearch(s, i, 0) + binarySearch(s, i, 1)
    return ans

Время работы

Изначальный подсчет хешей производится за [math]O(|s|)[/math]. Каждая итерация будет выполняться за [math]O(\log(|s|))[/math], всего итераций — [math]|s|[/math]. Итоговое время работы алгоритма [math]O(|s|+|s|\cdot \log(|s|)) = O(|s|\cdot \log(|s|))[/math].

Избавление от коллизий

У хешей есть один недостаток — коллизии: можно подобрать входные данные так, что хеши разных строк будут совпадать. Абсолютно точно проверить две подстроки на совпадение можно с помощью суффиксного массива, но с дополнительной памятью [math]O(|s|\cdot \log(|s|))[/math]. Для этого построим суффиксный массив для строки [math]s + \# + reverse(s)[/math], при этом сохраним промежуточные результаты классов эквивалентности [math]c[/math]. Пусть нам требуется проверить на совпадение подстроки [math]s[i..i + l][/math] и [math]s[j..j + l][/math]. Разобьем каждую нашу строку на две пересекающиеся подстроки длиной [math]2^k[/math], где [math]k = \lfloor \log{l} \rfloor[/math]. Тогда наши строки совпадают, если [math]c[k][i] = c[k][j][/math] и [math]c[k][i + l - 2^k] = c[k][j + l - 2^k][/math].

Итоговая асимптотика алгоритма: предподсчет за построение суффиксного массива и [math]O(\log(|s|))[/math] на запрос, если предподсчитать все [math]k[/math], то [math]O(1)[/math].

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

Идея

Алгоритм, который будет описан далее, отличается от наивного тем, что использует значения, посчитанные ранее. Будем поддерживать границы самого правого из найденных палиндромов — [math][l; r][/math]. Итак, пусть мы хотим вычислить [math]d1[i][/math] — т.е. длину наибольшего палиндрома с центром в позиции [math]i[/math]. При этом все предыдущие значения в массиве [math]d[/math] уже посчитаны. Возможны два случая:

1. [math]i \gt r[/math], т.е. текущая позиция не попадает в границы самого правого из найденных палиндромов. Тогда просто запустим наивный алгоритм для позиции [math]i[/math].
2. [math]i \leqslant r[/math]. Тогда попробуем воспользоваться значениями, посчитанным ранее. Отразим нашу текущую позицию внутри палиндрома [math][l;r] : j = (r - i) + l[/math]. Поскольку [math]i[/math] и [math]j[/math] — симметричные позиции, то если [math]d1[j] = k[/math], мы можем утверждать, что и [math]d1[i] = k[/math]. Это объясняется тем, что палиндром симметричен относительно своей центральной позиции. Т.е. если имеем некоторый палиндром длины [math]k[/math] с центром в позиции [math]l \leqslant i \leqslant r[/math], то в позиции [math]j[/math], симметричной [math]i[/math] относительно отрезка [math][l; r][/math] тоже может находиться палиндром длины [math]k[/math]. Это можно лучше понять, посмотрев на рисунок. Снизу фигурными скобками обозначены равные подстроки. Однако стоит не забыть про один граничный случай: что если [math]i + d1[j] - 1[/math] выходит за границы самого правого палиндрома? Так как информации о том, что происходит за границами это палинлрома у нас нет (а значит мы не можем утверждать, что симметрия сохраняется), то необходимо ограничить значение [math]d1[i][/math] следующим образом: [math]d1[i] = \min(r - i, d1[j])[/math]. После этого запустим наивный алгоритм, который будет увеличивать значение [math]d1[i][/math], пока это возможно.

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

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

Псевдокод

Приведем код, который вычисляет значения массива [math]d1[/math]:

// [math]s[/math] — исходная строка
int[] calculate1(string s):
  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
  return d1

Вычисление значений массива [math]d2[/math]:

// [math]s[/math] — исходная строка
int[] calculate2(string s):
  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
  return d2

Оценка сложности

Внешний цикл в приведенном алгоритме выполняется ровно [math]n[/math] раз, где [math]n[/math] — длина строки. Попытаемся понять, сколько раз будет выполнен внутренний цикл, ответственный за наивный подсчет значений. Заметим, что каждая итерация вложенного цикла приводит к увеличению [math]r[/math] на [math]1[/math]. Действительно, возможны следующие случаи:

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

Т.к. значение [math]r[/math] не может увеличиваться более [math]n[/math] раз, то описанный выше алгоритм работает за время [math]O(n)[/math].

См. также

• Префикс-функция
• Z-функция

Источники информации

• MAXimal :: algo :: Нахождение всех подпалиндромов
• Википедия — Поиск длиннейшей подстроки-палиндрома
• Алгоритмы для поиска палиндромов — Хабр