Python最長回文文字列アルゴリズム

この記事では主に Python の最長回文文字列アルゴリズムの実践を詳しく紹介します。興味のある方は参考にしてください。回文プロパティ。いわゆる回文とは、「aba」、「ababa」、「abba」などの文字列を指します。もちろん、1 つの文字と隣接する 2 つの同じ文字も回文の性質を満たします。

この問題を見たとき、最初に頭に浮かぶ解決策は、文字列内のすべての文字列の開始点を列挙することによって、回文を満たす部分文字列を 1 つずつ決定し、長さを記録し、その長さを更新することです。最長の長さ。明らかに、このアルゴリズムの時間計算量は非常に高く、最悪の場合は O(N*N) に達する可能性があります。したがって、ここでは、文字列の部分文字列の開始点の代わりに中心を列挙し、同時に両側に広げることによって、部分文字列の回文的性質を 1 つずつ判断する最適化された解決策を提案します。この最適化アルゴリズムは、最悪の場合 (つまり、文字が 1 つだけの文字列) の以前のアルゴリズムよりもはるかに効率的です。

上記の最適化計画から、中心を列挙する方が点を列挙するより効率的であることがわかりますが、これは最適なアルゴリズムではありません。中心を列挙するアルゴリズムは中心の両側の文字に同時に影響を与えるため、中心より左側の文字を中心として列挙し、部分文字列の回文を判定することで、部分文字列の回文を判定できます。中心より右側の文字を center として列挙します。これがマネージャーのアルゴリズムです。

manacher アルゴリズムのアイデアは非常に賢いもので、まず i が列挙の中心であると仮定して文字列を走査し、次に j (j ;=f[i']

2. i について j の影響範囲に対称文字 i' の影響範囲が完全に含まれていないとき、i の右側の影響範囲が大きくなります。または [j-f[j]/2,i'] に等しい、つまり i+f[i]/2> =i'-j+f[j]/2

対称性により、i+ を得ることができます。 i" = 2*j。したがって、最初のケースでは、f[i]>=f[2*j-i]; 2 番目のケースでは、f[i]>=f[j]+2*j-2 *i.

上記の 1,2 に基づいて、未探索があるため、f[i]>=min(f[2*j-i ],f[j]+2*j-2*i) を取得できます。 i の右側の文字は、最長の回文部分文字列が見つかるまで両側に展開し続けます

j+f[j]/2 以降も i が存在する場合、それは i が前の文字の影響を受けないことを意味します。両側に 1 つずつしか展開できません

このアルゴリズムは文字列を 1 回トラバースするだけでよく、時間計算量も O(N) に達する可能性があります

以下のプログラムです。 Pthon3. アルゴリズムの効率をテストするために、最悪のアルゴリズムの参照として、元の総当たり列挙アルゴリズムが引き続き提供されています。例として長さ 1000 でテストしました:

Violent enumeration: 49.719844s

Central enumeration: 0.334019s

manacher: 0.008000s

長さが 1000 の場合、暴力的なそれに比べて、中央の列挙の効率は大幅に向上し、最適なマネージャーの時間が短縮されました。

指定された文字列のすべてのサブシーケンスが回文シーケンスであるかどうかを判断する Python メソッド

以上がPython最長回文文字列アルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。