Урок: наибольшая палиндромная подстрока — зеркало одним куском

Вчера искали палиндром-подпоследовательность: буквы можно было пропускать. Сегодня жёстче — нужна непрерывная подстрока. В «babad» ответ «bab» (или «aba»): три буквы подряд, читаются одинаково в обе стороны. Вчерашний «BBBAB» тут дал бы только «BBB» или одиночную «A» — середину уже не выкинешь. Подстрока = сплошной кусок; подпоследовательность = можно прыгать по индексам. Это разные задачи, путать их на собеседовании дорого. Идея: expand around centers. У палиндрома есть центр. Для нечётной длины это буква (как «a» в «bab»), для чётной — щель между двумя одинаковыми (как между «b» и «b» в «bb»). Всего 2n−1 таких центров: n нечётных и n−1 чётных. Из каждого тянем указатели влево и вправо, пока символы совпадают и не вышли за края. Среди всех развёрток берём самую длинную — она и есть ответ. Время O(n2), дополнительная память O(1): кроме строки почти ничего не храним. Двумерная динамика тоже существует (O(n2) время и память на таблице булевых «отрезок i..j — палиндром?»), но для длины и индексов expand обычно короче и понятнее. На первой картинке — «babad». Центр на индексе 1 (буква «a»): сначала сам «a», потом соседи b=b → «bab», дальше слева край строки, справа «d» — стоп. Другие центры длиннее не дают; «aba» длины 3 тоже валиден, алгоритм просто нашёл «bab» раньше. Для «cbbd» срабатывает чётный центр между двумя «b» → «bb». Код — на второй картинке: вспомогательная expand возвращает полуинтервал [lo, hi), снаружи обновляем лучший. Запустили на Python 3.13.5: «babad» → bab; «cbbd» → bb; «forgeeksskeegfor» → geeksskeeg. Что важно помнить. — Подстрока ≠ подпоследовательность: здесь кусок обязан быть сплошным. — Не забывайте оба типа центров: иначе пропустите все чётные палиндромы вроде «aa». — Где встречается: классика собеседований и олимпиад, разбор строк, поиск «зеркальных» фрагментов в тексте. Идея в одной фразе: каждый возможный центр раздуваем, пока края совпадают, и запоминаем самый длинный кусок — так за квадрат времени находим наибольшую палиндромную подстроку без тяжёлой таблицы. #урок