Как найти максимальный палиндром в строке

Алгоритм поиска самой длинной подстроки-палиндрома

Один из самых прекрасных алгоритмов в информатике, который показывает, как можно получить большое ускорение от «вялого» O(n³) до молниеносного¹ O(n), просто посмотрев на проблему с другой точки зрения.

Задача состоит в том, чтобы найти самую длинную подстроку, которая является палиндромом (читается одинаково слева направо и справа налево, например, «racecar»). Так, самый длинный палиндром в строке «Fractions are never odd or even» это «never odd or even» (регистр букв и пробелы игнорируются). Это также имеет практическое применение в биохимии (ГААТТЦ или ЦТТААГ являются палиндромными последовательностями²). К тому же, эту задачу³ часто дают на собеседовании.

Самый простой и прямой подход (при этом самый медленный) — перебирать с начала все подстроки всех длин и проверять, является ли текущая палиндромом:

Псевдокод такого решения

ЦИКЛ по символам всей строки:
	ЦИКЛ по всем длинам, начиная с текущего символа:
		ЦИКЛ по символам в этой подстроке:

явно указывает, что метод со сложностью O(n³) (где n — это длина начальной строки) является быстровозрастающей функцией.

Если бы вместо перебора с самых начал подстрок, мы начинали перебор с середины, это позволило бы нам использовать результаты, которые мы получили на предыдущих шагах.

Например, если мы знаем, что «eve» — это палиндром, то нам потребуется всего одно сравнение, чтобы выяснить, что «level» тоже палиндром. В первом решении нам бы пришлось проверять все полностью с самого начала.

ЦИКЛ по символам строки до середины:
	ЦИКЛ по всем длинам, начиная с текущего символа:

В таком случае сложность составляет O(n²). Но существуют методы⁴, позволяющие сделать это еще быстрее.

Один из самых изящных — это алгоритм Манакера⁵. Он основан на методе, описанном выше, но его временная сложность сокращена до O(n).

Когда палиндромы в строке находятся далеко, оптимизировать нечего. Сложность и так O(n). Проблема появляется, когда они пересекаются, а худшим случаем является строка, состоящая из одной буквы.

Рассмотрим следующую ситуацию. Алгоритм нашел самый короткий зеленый палиндром, самый длинный голубой палиндром и остановился на букве «i»:

Внимательно посмотрев на картинку, можно заметить, что у нас нет необходимости обрабатывать правую часть голубого палиндрома. По определению, это зеркальное отражение левой части, так что полученную левую часть мы можем отразить на правую и получить ее, так сказать, «за бесплатно».

Однако, это не единственный случай перекрытия. На следующей картинке зеленый палиндром пересекает границу голубого, поэтому его длина должна быть уменьшена.

Опять-таки нет нужды дважды проверять длину отраженного палиндрома: буквы b и x обязаны быть различными, иначе голубой палиндром был бы длиннее.

Наконец, один палиндром может «касаться» другого изнутри. В этом случае нет гарантий, что отраженный палиндром не имеет бОльшую длину, так как мы получаем нижнюю границу его длины:

В идеале мы должны пропускать как нулевые, так и строго ненулевые значения (= все случаи, кроме последнего) в дальнейшей обработке (код 1 ниже). Но в практике (если вообще можно говорить о практике в такой абстрактной задаче) разница между ≥ и = довольно мала (всего одно дополнительное сравнение), поэтому имеет смысл рассматривать все ненулевые значения с помощью ≥ для краткости и читаемости кода (код 2 ниже).

Одна из возможных реализаций алгоритма на питоне:

#код 1
def odd(s):
    n = len(s)
    h = [0] * n
    C = R = 0      # центр и радиус или крайний правый палиндром
    besti, bestj = 0, 0     # центр и радиус самого длинного палиндрома
    for i in range(n):
        if i < C + R:         # если есть пересечение
            j = h[C-(i-C)]       # отражение
            if j < C + R - i:    # случай A
                h[i] = j
                continue
            elif j > C + R - i:  # случай B 
                h[i] = C + R - i
                continue
            else:                # case C 
                pass
        else:                 # если нет пересечения
            j = 0
        while i-j > 0 and i+j<n-1 and s[i-j-1] == s[i+j+1]:
            j += 1
        h[i] = j
        if j > bestj:
            besti, bestj = i, j
        if i + j > C + R:
            C, R = i, j
    return s[besti-bestj : besti+bestj+1]

Сперва алгоритм пытается найти соответствующее отражение, как описано выше. Затем, если необходимо, последовательно ищет: как в алгоритме со сложностью O(n²), но принимая отраженное значения за начальную точку. В конце если новый палиндром перекрывает больше текста справа, чем предыдущий, то он становится новым крайним правым палиндромом.

Эта функция ищет палиндромы только нечетного размера. Общий подход для работы с палиндромами четного размера таков:

• вставлять произвольный символ между символами в оригинальной строке, к примеру ‘noon’ -> ‘|n|o|o|n|’,

• находить палиндром нечетного размера,

• удалять произвольные символы из результата.

Символ «|» необязательно должен отсутствовать в строке. Можно использовать любой символ.

def odd_or_even(s):
    return odd('|'+'|'.join(s)+'|').replace('|', '')

>>> odd_or_even('afternoon')
'noon'

Немного запутанная версия (труднее для понимания, немного медленнее, но короче) выглядит так:

#код 2
import re

def odd(s):
    n = len(s)
    h = [0] * n
    C = R = 0      # центр и радиус или крайний правый палиндром
    besti, bestj = 0, 0     # центр и радиус самого длинного палиндрома
    for i in range(n):
        j = 0 if i > C+R else min(h[C-(i-C)], C+R-i)
        while i-j > 0 and i+j<n-1 and s[i-j-1] == s[i+j+1]:
            j += 1
        h[i] = j
        if j > bestj:
            besti, bestj = i, j
        if i + j > C + R:
            C, R = i, j
    return s[besti-bestj : besti+bestj+1]

def manacher(s):
    clean = re.sub('W', '', s.lower())
    return odd('|'+'|'.join(clean)+'|')[1::2]

>>> manacher('He said: "Madam, I'm Adam!"')
'madamimadam'

Как видно, в коде есть два вложенных цикла. Тем не менее, интуитивно понятно, почему сложность O(n). На диаграмме показан массив h.

Внешний цикл соответствует горизонтальному перемещению, внутренний — вертикальному. Каждый шаг — это одно сравнение. Сплошные линии — расчет шагов, пунктирные — пропуск шагов.

Очевидно из диаграммы, что, когда палиндромы не пересекаются, число шагов «вверх» равно количеству горизонтальных «пропускающих» шагов. Для пересекающихся палиндромов чуть более заморочено, но если посчитать число шагов «вверх» и число горизонтальных «пропускающих шагов, то эти числа вновь совпадут. Так что общее число шагов ограничено 2n сравнениями. Не просто n , потому что, в отличие от вертикальных шагов, чтобы понять, пропускать ли горизонтальный шаг или нет, необходимо проделать некую работу (хотя можно изменить реализацию, чтобы пропускать их за постоянное время). Итого временная сложность — O(n).

Алгоритм Манакера позволяет найти самый длинный палиндром в строке (если быть точнее, не просто самый длинный палиндром, а самый длинный палиндром для всех возможных центров) за линейное время, используя очень интуитивный подход, лучше всего описываемый визуально.

Ссылки:

1. Сайт Big-O Cheat Sheet.

2. Статья на Википедии про палиндромные последовательности.

3. Задача на Leetcode про самый длинный палиндром в строке.

4. Статья на Википедии про самый длинный палиндром в строке.

5. Гленн Манакер (1975), «Новый линейный алгоритм для поиска самого длинного палиндрома строки», журнал ACM.

Например, HELOLEH является подпоследовательностью-палиндромом строки HTEOLFEOLEH.

Решение

Обозначим данную последовательность через , а ее элементы — через , где — длина строки . Будем рассматривать возможные подпоследовательности данной последовательности с го по ый символ включительно, обозначив её как . Длины максимальных подпалиндромов для данной последовательности будем записывать в двумерный массив : — длина максимальной подпоследовательности-палиндрома, который можно получить из последовательности .

Начнем решать задачу с простых подпоследовательностей. Для последовательности из одного элемента (то есть подпоследовательности вида ) ответ очевиден — ничего вычеркивать не надо, такая строка будет искомой подпоследовательностью-палиндромом. Для последовательности из двух элементов возможны два варианта: если элементы равны, то мы имеем подпоследовательность-палиндром, ничего вычеркивать не надо. Если же элементы не равны, то вычеркиваем любой.

Пусть теперь нам дана подпоследовательность . Если и элементы подпоследовательности не совпадают, то один из них нужно вычеркнуть. Тогда у нас останется подпоследовательность или — то есть мы сведем задачу к подзадаче: . Если же первый и последний элементы равны, то мы можем оставить оба, но необходимо знать решение задачи . Таким образом получаем следующее рекуррентное соотношение:

Асимптотика

Каждый элемент массива мы вычисляем раз за обращаясь к уже вычисленным элементам. Так как размер массива , то алгоритм работает за

Пример

Рассмотрим решение на примере последовательности ABACCBA. Первым делом заполняем диагональ массива единицами, они будут соответствовать подпоследовательностями из одного элемента. Затем начинаем рассматривать подпоследовательности длины два. Во всех подпоследовательностях, кроме , элементы различны, поэтому в соответствующие ячейки запишем , а в — .

Получается, что мы будем заполнять массив по диагоналям, начиная с главной диагонали. Для подпоследовательностей длины получаются следующие значения: в подпоследовательности ABA первый и последний элемент равны, поэтому . В остальных подпоследовательностях первый и последний элементы различны.

BAC:

ACC:

CCB:

CBA:

Продолжая далее аналогичные рассуждения, заполним все ячейки над диагональю и в ячейке получим ответ — .

Если же в задаче необходимо вывести не длину, а саму подпоследовательность-палиндром, то дополнительно к массиву длин мы должны построить массив переходов — для каждой ячейки запомнить, какой из случаев был реализован.

Последовательность заполнения массива и массив переходов см. на изображениях ниже.

Псевдокод

Перед вызовом процедуры заполняем начальными значениями: если , , если , в остальных случаях .
При первом вызове функции в качестве аргументов передаем индексы первого и последнего элементов исходной строки. Например для строки длиной вызов функции будет иметь следующий вид: . Искомая же длина будет записана в ячейке .

Функция для вычисления длины палиндрома:

• Границы исходной последовательности:

 int palSubSeq(left: int, right: int):
   if L[left][right] == -1 
     if s[left] == s[right] 
       L[left][right] = palSubSeq(left + 1, right - 1) + 2
     else 
       L[left][right] = max(palSubSeq(left + 1, right), palSubSeq(left, right - 1))  
   return L[left][right]

Процедура для построения искомого палиндрома:

• Границы исходной последовательности:
• Границы искомой подпоследовательности-палиндрома, где правой границей будет длина найденного палиндрома:

 // palindrome — массив символов, где в palindrome[i] содержится символ искомой последовательности-палиндрома
 palChars(left: int, right: int, palLeft: int, palRight: int):
   while left  right
     if left == right and L[left][right] == 1
       palindrome[palLeft++] = S[left++]
     else
       if S[left] == S[right]
         palindrome[palLeft++] = S[left++]
         palindrome[palRight--] = S[right--]
       else
         if L[left + 1][right]  L[left][right - 1]
           left++
         else
           right--

См. также

• Задача о наибольшей общей подпоследовательности
• Задача о наибольшей возрастающей подпоследовательности
• Задача о наибольшей общей палиндромной подпоследовательности

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

• Википедия — Палиндром
• Wikipedia — Palindrome
• Wikipedia — Longest palindromic subsequence