最長の回文部分文字列

コンピュータサイエンスにおいて、最長回文部分文字列または最長対称因子問題とは、与えられた文字列の中で、連続する部分文字列のうち、回文でもある最長の部分文字列を見つける問題です。例えば、「bananas」の最長回文部分文字列は「anana」です。最長回文部分文字列は一意であるとは限りません。例えば、「abracadabra」という文字列には、長さが3を超える回文部分文字列はありませんが、長さが3の回文部分文字列は「aca」と「ada」の2つあります。アプリケーションによっては、1つの部分文字列だけを返す、あるいは回文部分文字列の最大長を返すのではなく、すべての最大回文部分文字列（つまり、それ自体が回文であり、より大きな回文部分文字列に拡張できないすべての部分文字列）を返す必要がある場合があります。

マナカー（1975）は${\displaystyle O(n)}$指定された長さの文字列の先頭に現れるすべての回文を列挙する時間アルゴリズム${\displaystyle n}$しかし、例えばApostolico、Breslauer & Galil (1995)が指摘しているように、同じアルゴリズムは入力文字列内の任意の場所にある最大回文部分文字列をすべて見つけるためにも使用できます。${\displaystyle O(n)}$時間。したがって、それは${\displaystyle O(n)}$最長回文部分文字列問題に対する時間解法。代替案${\displaystyle O(n)}$時間の解は、 Jeuring (1994)とGusfield (1997)によって提供され、Gusfield は接尾辞木に基づく解を説明した。ワード RAMモデルの計算では、サイズが小さい場合、より高速なアルゴリズムが実現できる。${\displaystyle \sigma }$入力アルファベットの$2^{o(\log n)}}$特に、このアルゴリズムは${\displaystyle O(n\log \sigma /\log n)}$時間を使う${\displaystyle O(n\log \sigma /\log n)}$空間。^{[ 1 ]}この問題に対する効率的な並列アルゴリズムも知られています。 ^{[ 2 ]}

最長回文部分文字列問題は、最長回文部分列を見つけるという別の問題と混同してはならない。

このアルゴリズムはマナチャーのアルゴリズムよりも処理速度は遅いものの、マナチャーのアルゴリズムを理解するための良い足がかりとなる。各文字を回文の中心とみなし、その中心を持つ最大の回文を決定するためにループ処理を行う。

関数の中央にあるループは、長さが奇数の回文に対してのみ機能します。偶数の長さの回文に対しては、入力文字列を変更することで機能します。入力文字列の各文字間と両端に「|」文字が挿入されます。したがって、入力「book」は「|b|o|o|k|」になります。「book」内の偶数の長さの回文「oo」は、奇数の長さの回文「|o|o|」になります。

// C言語の擬似コード。Longest_Palindrome_SLOW (文字列S 、文字列R ) {// R == S に偽文字 (例: '|') を挿入// 各文字間（外側の境界を含む）// R の各位置を中心とする最長回文の半径// 注: length(R) = length(PalindromeRadii) = 2 × length(S) + 1配列PalindromeRadii = [ 0 ,..., 0 ]中心= 0Center < length ( R )の間{// 最長の回文を決定する// 中心半径の位置から中心+半径へ移動半径= 0中心- (半径+ 1 ) > = 0かつ中心+ (半径+ 1 ) <長さ( R )かつR [中心- (半径+ 1 )] = R [中心+ (半径+ 1 )] {半径=半径+ 1}// 配列内の最長回文の半径を保存するPalindromeRadii [中心] =半径中央=中央+ 1}// longest_palindrome_in_S は max(PalindromeRadii) であることが示せる。// R[i] == '|' の場合、PalindromeRadii[i] は偶数になります。そうでない場合は、PalindromeRadii[i] を 1 増やすことができます。// これは、各境界線に余分な「|」を挿入することと同じです。// R の '|' を中心とする回文は、S の偶数回文に対応することに注意してください。// R[i] != '|' の場合、PalindromeRadii[i] は奇数 (同じ引数) であり、奇数回文に対応します。// この場合、回文の長さ// その文字を中心とするのは x=PalindromeRadii[i] でもあり、両側に (x-1)/2 文字あります。// 加えて中央の余分なもの ((x-1)/2*2+1=x)S における最長回文= max (回文半径)S で最長の回文を返す}

このアルゴリズムの実行時間は${\displaystyle O(n^{2})}$外側のループが実行されます${\displaystyle n}$回、そして内側のループは最大で${\displaystyle n/2}$回。

以下はマナチャーのアルゴリズムの擬似コードです。このアルゴリズムは、回文の中に別の回文が含まれている場合を利用するため、以前のアルゴリズムよりも高速です。

例えば、入力文字列「abacaba」を考えてみましょう。「c」に到達するまでに、マナチャーのアルゴリズムは「c」より前の文字を中心としたすべての回文の長さを特定します。「c」では、ループを実行して「c」を中心とした最大の回文「abacaba」を特定します。この情報があれば、「c」以降のすべては「c」より前のすべてのものの鏡像のように見えます。「c」の後の「a」は、「c」の前の「a」と同じ最長の回文を持ちます。同様に、「c」の後の「b」は、 「c」の前の「b」を中心とした最長の回文の長さ以上の長さを持つ最長の回文を持ちます。考慮すべき特殊なケースはいくつかありますが、この手法によって計算速度が劇的に向上します。

// C言語の擬似コード。最長回文(文字列S 、文字列R ) {// R == S に偽文字 (例: '|') を挿入// 各文字間（外側の境界を含む）// R の各位置を中心とする最長回文の半径// 注: length(R) = length(PalindromeRadii) = 2 × length(S) + 1配列PalindromeRadii = [ 0 ,..., 0 ]中心= 0半径= 0Center < length ( R )の間{// ループの開始時点で、半径は既に下限値に設定されている// 最長半径の場合。最初の反復では、半径は 0 ですが、// 後続の反復では、値が高くなることがあります。// 中心半径から始まる最長の回文を決定します。// 中心+半径へ移動中心- (半径+ 1 ) > = 0かつ中心+ (半径+ 1 ) <長さ( R )かつR [中心- (半径+ 1 )] = R [中心+ (半径+ 1 )] {半径=半径+ 1}// 配列内の最長回文の半径を保存するPalindromeRadii [中心] =半径// 以下では、Center が増加します。// 事前に計算された値が再利用できる場合は、再利用します。// また、半径は0より大きい値に設定することもできます。旧センター＝センターOldRadius =半径中央=中央+ 1// 半径のデフォルト値は、// 次のループ。半径= 0センターがOldCenter + OldRadius以下である間{// なぜなら、センターは古い回文の中にあり、// 回文内の文字は「鏡像」文字を持つ// 中心を横切って反射したデータを使用できます// 中心のミラーポイントに対して事前に計算されています。ミラーセンター=旧センター- (センター-旧センター)MaxMirroredRadius = OldCenter + OldRadius - CenterPalindromeRadii [ MirroredCenter ] < MaxMirroredRadiusの場合{// MirroredCenter を中心とした回文は完全に// OldCenter を中心とした回文の中に含まれています。したがって、// MirroredCenter と Center は同じサイズの回文を持つPalindromeRadii [ Center ] = PalindromeRadii [ MirroredCenter ]中央=中央+ 1} else if PalindromeRadii [ MirroredCenter ] > MaxMirroredRadius {// MirroredCenter の回文は、// OldCenter の回文 Center の回文は// OldCenter 回文の端で終了する。そうでない場合は、// OldCenter の回文はもっと大きいだろうPalindromeRadii [ Center ] = MaxMirroredRadius中央=中央+ 1} else { // PalindromeRadii[MirroredCenter] = MaxMirroredRadius// MirroredCenter の回文はちょうど// OldCenter を中心とする回文の端、// 中央の回文はもっと大きいかもしれません。半径を// 中央の回文の最小サイズなので、// 不必要に再チェックする半径= MaxMirroredRadius壊す}}}// 回文のサイズは半径 * 2 に等しい。ただし、// 変数 Radius は、偽の文字を横に考慮します// 中央、対応する回文のサイズは実際には 2 *// (半径 / 2) は、回文のサイズがその半径 / 2 に等しいことを意味します。// PalindromeRadii における対応する半径値S における最長回文= max (回文半径)S で最長の回文を返す}

• 回文の木

• Apostolico, Alberto; Breslauer, Dany; Galil, Zvi (1995)、「文字列中のすべての回文の並列検出」、Theoretical Computer Science、141 ( 1–2 ): 163–173、doi : 10.1016/0304-3975(94)00083-U。
• Charalampopoulos, Panagiotis; Pissis, Solon P.; Radoszewski, Jakub (2022)、「準線形時間で最長の回文部分文字列」、第33回組み合わせパターンマッチングに関する年次シンポジウム、CPM 2022、2022年6月27日～29日、チェコ共和国プラハ、223 : 20:1–20:9、doi : 10.4230/LIPIcs.CPM.2022.20。
• Crochemore, Maxime; Rytter, Wojciech (1991)、「文字列と配列の並列計算におけるKarp–Miller–Rosenbergアルゴリズムの有用性」、Theoretical Computer Science、88 (1): 59– 82、doi : 10.1016/0304-3975(91)90073-B、MR 1130372 。
• Crochemore, Maxime; Rytter, Wojciech (2003)、「8.1 対称語の探索」、Jewels of Stringology: Text Algorithms、World Scientific、pp. 111–114、ISBN  978-981-02-4897-0。
• Gusfield, Dan (1997)、「9.2 線形時間で全ての最大回文を見つける」、Algorithms on Strings, Trees, and Sequences、ケンブリッジ：ケンブリッジ大学出版局、pp. 197–199、doi：10.1017/CBO9780511574931、ISBN  0-521-58519-8MR 1460730​ 。
• Jeuring, Johan (1994)、「オンラインアルゴリズムの導出と回文の探索への応用」、Algorithmica、11 (2): 146–184、doi : 10.1007/BF01182773、hdl : 1874/20926、MR 1272521、S2CID 7032332  。
• マナチャー、グレン（1975）「文字列の最小初期回文を見つけるための新しい線形時間「オンライン」アルゴリズム」、Journal of the ACM、22（3）：346–351、doi：10.1145/321892.321896、S2CID 10615419 。
•  この記事には、CC BY 3.0ライセンスの下で利用可能な最長回文部分文字列テキストが含まれています。

• 最長回文部分文字列 パートII。 、2011年11月20日、 2018年12月8日にオリジナルからアーカイブ済み線形時間で最長の回文部分文字列を見つけるためのマナチャーのアルゴリズムの説明。
• Akalin, Fred (2007-11-28)、「線形時間で最長の回文部分文字列を見つける」 、 2016-10-01取得マナチャーの線形時間アルゴリズムの説明とPythonによる実装。
• Jeuring, Johan (2007–2010), Palindromes 、 2011年11月22日取得Jeuringの線形時間アルゴリズムのHaskell実装。
• 回文（リンク切れ）。マナチャーの線形時間アルゴリズムのJava実装。