Для заданной строки найдите самую длинную палиндромную подстроку.
Что такое палиндром?
Строка-палиндром читается одинаково как вперед, так и назад
Например: «абба», «абба».
Мы ищем подстроку, которая является палиндромом, а не подпоследовательностью (есть разница)
Эти вопросы имеют сходство с вопросом о поиске самой длинной палиндромной подпоследовательности, которую можно решить с помощью динамического программирования. Поскольку подстрока также является подпоследовательностью, мы можем применить тот же алгоритм с небольшими изменениями, чтобы найти самую длинную палиндромную подстроку, но решение будет 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#@»
$ и @ помогут справиться с выходными условиями.
Удачного кодирования!!!