Manacherのアルゴリズム

Question

Manacherのアルゴリズムを実装している最中のPalindromic Substringでは、マーカー記号（指定された文字列の間の記号）を使用する必要がありますか？

もしそうなら、256個のシンボルがすべて使い果たされたらどうなりますか？

Answer 1

個人的には、自分自身のアルゴリズムはすでに十分に難しいと思います。マーカーなしでそれを行うことができれば、コードはあまり理解できないように見えます。

幸運にも意味がありません。このアルゴリズムは、任意のタイプの配列に対して機能します。文字列のように、単なる文字の配列です。文字列を解析して、選択したエンコーディングに適した型の配列に変換してください。データ型のサイズに拘束される複雑さはありません。

Answer 2

Manacherアルゴリズムはpalindromのプロパティを使用して、中心を中心に対称です。ファインディングセンターは、奇妙な長さの文字列の場合、比較的単純です。偶数の長さの文字列に文字を追加すると、文字列の長さが奇数になるだから、あなたの文字列が偶数の長さの場合、文字を追加する必要があります