与えられた文字列中で最長の回文を見つける最良のアルゴリズムはどれですか？

Question

可能性の重複： 'n' の長さの文字列を考えると
Write a function that returns the longest palindrome in a given string

、私はその時間と空間の複雑さ、効率的であるべき最長の回文を必要としています。

誰でも少なくとも疑似コードで私を助けることができますか？

Answer 1

文字列内の各文字を回文の「中央」として考えて、左の位置の文字が右の位置の文字と等しい限り左右に展開する方法がありますサブストリングがパリンドロームであることの要件、明らかにサブストリングの2つのサブケースを奇数および偶数の長さとみなさなければならない）。ソース文字列中のすべての位置1..nに対してこれを行うと、文字列に含まれる連続する文字から最長の回文が得られます。