Самая длинная палиндромная подстрока и суффикс

Да, поиск самого длинного палиндрома с использованием алгоритмов, подобных LCS, не является хорошим способом, я не внимательно прочитал ссылочный ответ, но эта строка в ответе совершенно неверна:

Таким образом, самый длинный содержащийся палиндром в строке — это в точности самая длинная общая подстрока этой строки и ее реверс.

но если вы прочитали это и у вас есть встречный пример, не беспокойтесь об этом (вы правы на 99%), это распространенная ошибка, но простой способ заключается в следующем:

Запишите строку (barbapapa) следующим образом: #b#a#r#b#a#p#a#p#a#, теперь пройдите каждый символ этой новой строки слева направо, проверьте ее слева и справа, чтобы проверить, является ли это центром палиндрома или нет. Этот алгоритм в худшем случае равен O(n^2) и работает совершенно корректно. но обычно находит палиндром за O (n) (конечно, доказать это в среднем случае сложно). В худшем случае это строки со слишком большим количеством длинных палиндромов, таких как aaaaaa...aaaa.

Но есть лучший подход, который занимает O(n) времени, в основе этого алгоритма лежит Manacher. Связанный алгоритм более сложен, чем то, что я видел в вашем ответе, на который есть ссылка. Но то, что я предложил, является базовой идеей алгоритма Манахера, с умными изменениями в алгоритме вы можете пропустить проверку всех левых и правых (также есть алгоритмы с использованием суффиксных деревьев).

P.S: Я не мог видеть вашу ссылку на Algo из-за ограничений моего интернета, я не знаю, правильно это или нет.

Я добавил свое обсуждение с ОП, чтобы прояснить алгоритм:

let test it with barbapapa-> #b#a#r#b#a#p#a#p#a#, start from first #
there is no left so it's center of palindrome with length 1.
Now "b",has # in left and # in right, but there isn't another left to match with right 
so it's a center of palindrome with length 3.
let skip other parts to arrive to first "p":
first left and right is # second left and right is "a", third left and
right is # but forth left and right are not equal so it's center of palindrome
of length 7 #a#p#a# is palindrome but b#a#p#a#p is not 
Now let see first "a" after first "p" you have, #a#p#a#p#a# as palindrome and this "a" 
is center of this palindrome with length 11 if you calculate all other palindromes 
length of all of them are smaller than 11

Также использование # связано с рассмотрением палиндромов четной длины.

Найдя центр палиндрома во вновь созданной строке, найдите связанный палиндром (зная центр и его длину), затем удалите #, чтобы узнать самый большой палиндром.