対数実行時の複雑さにおける最長のパリンドロームのサブストリング

Question

サイズNのパリンドロームでは、最長パリンドロームの候補量はN ^ 2です。したがって、情報理論的下限（IBT）はLG（N ^ 2）でなければならず、これはLG（N）のランタイムの複雑さに相当します。

IBTにより、比較ベースのアルゴリズムを使用していて、それを適用するための決定木について考えることを意味し、その木の葉はすべての可能性（N ^ 2葉）、したがってその木の高さになります。lg（n ^ 2）です。ただし、この実行時の複雑さでこの質問を解決することができるアルゴリズムを見つけることができませんでした。私が見つけた最高のものは、線形時間で質問を解決するマナーのアルゴリズムです。

Answer 1

あなたのa palindrome $ p $ のサイズ $ n $ を与えられている場合（あなたが言うように質問の始めに、最長のPalindromeは $ p $ それ自体で、あなたは計算をする必要はありません。

入力がPalindromeではなく任意の文字列ではない場合は、少なくとも入力を読み取る必要がありますので、 $ \ omomega（n）$ は簡単です下限