Для этого есть так много решений, и лучше всего решить с помощью «Алгоритма Манахера».
Я пишу одно из решений, которое прекрасно работает и его легко понять. Надеюсь, вы это поймете.
У нас есть два случая: палиндром либо нечетной длины, либо четной длины.
Например: дана строка s = «babad», s1 = «cbbd». Нам нужно найти самую длинную палиндромную подстроку.
Для строки s ответом будет «bab», а для s1 — «bb».
Рассмотрим пустую строку, здесь answer = “”, и предположим, что она имеет наибольшую длину. Теперь для обоих случаев, четной и нечетной длины, мы найдем палиндромную подстроку.
Для нечетной длины у нас будет один центр, то есть только i, но это не так для четной длины. У нас есть два центра для проверки, i и i + 1.
Чтобы найти палиндром, мы создадим функцию palindrome(), которая будет содержать 3 параметра: строку, левый индекс и правый индекс. Для нечетной длины левый и правый индексы будут одинаковыми, но для четной длины, если левый равен i, то правый будет i + 1.
нечетное = палиндром (s, i, i) четное = палиндром (s, i, i+1)
Предполагая, что левый и правый индексы равны нулю. Повторяем цикл, пока не найдем палиндром и не вернем подстроку.
Теперь нам нужно проверить, что длина нечетной строки больше длины четной строки. Если нечетное больше четного, мы присвоим его переменной с именем big, а затем будем проверять big с нашей пустой строкой, пока не получим самую длинную палиндромную строку.
Надеюсь, вы, ребята, поняли это. Если у вас есть какие-либо сомнения, пожалуйста, прокомментируйте ниже.
Спасибо, что прочитали это.
