Найдите максимальную по длине палиндромную подстроку

Классическая задача. Найдите в данной вам строке максимальную по длине подстроку, которая является палиндромом (то есть читается слева направо и справа налево одинаково). Предложите как можно более эффективный алгоритм.

Решение за О(n²) и О(1) памяти: перебор

Очевидное квадратичное решение приходит в голову практически сразу. У каждого палиндрома есть центр: символ (или пустое место между двумя соседними символами в случае палиндрома четной длины), строка от которого читается влево и вправо одинаково. Например, для палиндрома abacaba таким центром является буква c, а для палиндрома colloc — пространство между двумя буквами l. Очевидно, что центром нашей искомой длиннейшей палиндромной подстроки является один из символов строки (или пространство между двумя соседними символами), в которой мы производим поиск.

Теперь мы можем реализовать такое решение: давайте переберем все символы строки, для каждого предполагая, что он является центром искомой самой длинной палиндромной подстроки. То есть предположим, что на данный момент мы стоим в i-ом символе строки. Теперь заведем две переменных left и right, изначально left = i - 1 и right = i + 1 для палиндромов нечетной длины и i - 1, i соответственно для палиндромов четной длины. Теперь будем проверять, равны ли символы в позициях строки left и right. Если это так, то уменьшим left на 1, а right увеличим на 1. Будем продолжать этот процесс до тех пор, пока символы в соответствующих позициях станут не равны, или же мы не выйдем за границы массива. Это будет означать, что мы нашли самый длинный палиндром в центре с i-ым символов в случае для палиндрома нечетной длины и в пространстве между i-ым и i - 1-ым символом в случае палиндрома четной длины. Выполним такой алгоритм для всех символов строки, попутно запоминая найденный максимум, и таким образом мы найдем самую длинную палиндромную подстроку всей строки.

Докажем, что это решение работает за O(n²). Рассмотрим строку ааааааааааааааа… Для каждого ее символа мы будем двигать left и right, пока не выйдем за границы массива. То есть для первого символа мы сделаем 0*2 (умножение на 2 происходит, потому что мы выполняем алгоритм два раза — для палиндромов нечетной и четной длины) итераций, для второго 1*2, для третьей 2*2, и т.д. до центра, потом кол-во итераций станет уменьшаться. Это арифметическая прогрессия с разностью 2. Рассмотрим сумму этой арифметической прогрессии до середины строки. Как известно, сумма арифметической прогрессии имеет формулу (A1+An)/2*n. В нашем случае A1 = 0, An = n/2*2 = n. (0+n)/2*n = n/2*n = O(n²). Для убывающей части все аналогично, там тоже получится O(n²). O(n²)+O(n²) = O(n²), ч.т.д.

Решение за О(n log n) по времени и О(n) памяти: полиномиальный хэш + бинпоиск

Это решение является ускоренной модификацией предыдущего. Можно посчитать для строки полиномиальный хеш, замечательным свойством которого является то, что мы можем за О(1) получить хеш любой подстроки, а значит, посчитав его для оригинальной и перевернутой строки мы можем за О(1) проверить, является подстрока [l..r] палиндромом (реализацию можно найти здесь). Следующее замечание состоит в том, что для каждого центра при переборе подстрока на некотором количестве итераций сначала будет являться палиндромом, а затем всегда нет. А это значит, что мы можем воспользоваться бинпоиском: переберем все символы, для каждого бинпоиском найдем максимальную палиндромную подстроку с центром в нем, по ходу дела будем запоминать найденный максимум.

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

Решение за О(n) времени и O(n) памяти: алгоритм Манакера

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