Для заданной строки найдите самую длинную палиндромную подстроку.

Что такое палиндром?

Строка-палиндром читается одинаково как вперед, так и назад

Например: «абба», «абба».

Мы ищем подстроку, которая является палиндромом, а не подпоследовательностью (есть разница)

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

Есть более простое решение этой проблемы.

Ключевые наблюдения

  • Палиндром симметричен относительно центра.

Таким образом, мы можем рассматривать каждую точку как центр и пытаться расширяться вокруг нее.

Пример

  • «Эфеабкбафе»
  • “e|f|e|a|b|c|c|b|a|f|e”
  • Всего имеется 21 центр, считайте воображаемый центр между символами, чтобы справиться даже с палиндромным случаем.

Кодировать это решение проще.

Есть еще одно решение проблемы, которое решает это с временной сложностью O (N).

Алгоритм называется Алгоритм Манахера.

Это решение не ожидается во время собеседования!!!

Но все же это хороший алгоритм.

Попробуем разобраться в алгоритме.

Этот алгоритм использует свойство палиндрома, заключающееся в том, что палиндром симметричен относительно центра.

Мы будем поддерживать длину палиндрома для каждого центра.

«…АБАБАБА…»

Допустим, мы перебираем подстроку в заданной строке, которая является палиндромом с центром C, скажем, L и R обозначают границу этого палиндрома.

[L…C…R]

Предполагая, что мы уже знаем длину палиндрома каждого центра до C.

Для каждого нового центра I после C длина его палиндрома будет зависеть от зеркала I относительно C и правой границы R

P[I] = MIN(P[Зеркало I], R-I)

как найти зеркало I относительно центра C?

Допустим, я’ — это зеркало, поэтому I-C=C-I’ => I’ = 2*C-I

всякий раз, когда наш текущий палиндром выходит за границу, нам нужно изменить центр и его границу на текущий палиндром.

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

Этот алгоритм работает только для палиндрома нечетной длины, чтобы исправить это, мы добавили # между каждым символом находится строка

  • Инициализируем C, R (нам не нужен L при реализации) (строка 5)
  • для каждого индекса я нахожу его зеркальный индекс относительно C, назовем его MI (строка 9)
  • P[I] = MIN(P[MI], R-I) (строка 11)
  • Попробуйте расширить текущий палиндром в центре I. (Строка 13)
  • Если текущий палиндром выходит за границу R, то сбросить C и R до текущего палиндрома. (строка 14)
  • Сохраняйте палиндром максимальной длины, видимый до сих пор (строка 18)

Для упрощения решения давайте добавим символ перед каждым символом в строке. При этом нам не нужно отдельно обрабатывать нечетные и четные случаи, а также это упростит кодирование.

«абаба» =› «$#a#b#a#b#a#@»

$ и @ помогут справиться с выходными условиями.

Удачного кодирования!!!