algorithm - 特定の文字列で最長の回文を見つけるための最良のアルゴリズムはどれですか？

Question

重複の可能性：
指定された文字列で最長の回文を返す関数を記述します

'n'の長さの文字列を考えると、時間と空間の複雑さが効率的であるはずの最長の回文が必要です。

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

Answer 1

1 つのアプローチは、文字列内の各文字を可能な限り回文の「中心」と見なし、左位置の文字が右位置の文字と等しい限り、左右に拡張することです (これは、サブストリングが回文であるためには、明らかに、サブストリングの長さが奇数と偶数の 2 つのサブケースを考慮する必要があります)。ソース文字列のすべての位置 1..n に対してこれを行うと、文字列に含まれる連続した文字から最長の回文が得られます。