1. 概要

文字列の問題を扱うとき、回文と呼ばれる用語に出くわします。

このチュートリアルでは、回文とは何かを示します。 また、文字列内の回文部分文字列を処理するMahacherのアルゴリズムについても説明します。

最後に、Manacherのアルゴリズムを使用するいくつかのアプリケーションを紹介します。

2. 定義

2.1. 回文の定義

まず、回文とは何かを定義する必要があります。 パリンドローム文字列は、前方と後方を読み取るときに同じです。 たとえば、文字列{、、、}は回文ですが、{、}はそうではありません。

この定義から、回文の中心を定義できます。 回文の中心は、それを半分に分割する弦の中央です。 これらの半分のそれぞれは、他のの鏡像です。

次の例を見てみましょう。

ご覧のとおり、奇数長のパリンドロームの場合、中心はパリンドローム自体の要素です。 中央の前の部分は回文の左側と呼ばれます。 同様に、中央以降の部分を右側と呼びます。

ただし、偶数長のパリンドロームの場合、中心要素はありません。 代わりに、回文の左側と右側があります。

どちらの場合も、回文の右側は左側の鏡像です。 つまり、左側と右側は互いに逆になっています。

考慮すべきもう1つの注意点は、文字列が回文である場合、から最初と最後の文字を削除すると、回文文字列も取得されるということです。

同様に、文字列が回文である場合、同じ文字を最初と最後に追加すると、同様に回文文字列になります。

これらのプロパティは、後でアルゴリズムを確認すると便利です。

2.2. 問題の定義

回文についての理解が深まったので、Manacherのアルゴリズムが解決する問題を説明できます。

最初は、問題によって文字列が得られます。 その後、問題により、2つの配列とを計算するように求められます。 両方の配列は、各インデックスを中心とする最長のパリンドロームサブストリング（LPS）の表示を格納する必要があります。

結果として、は、中心がインデックスにある最長の奇数長の回文になります。 同様に、左側の最後の文字がインデックスにあるように、最長の偶数長の回文になります。

まず、この問題を解決するための素朴なアプローチについて説明します。 その後、Manacherのアルゴリズムが素朴なアプローチに対して行う最適化について説明します。

3. 素朴なアプローチ

素朴なアプローチは簡単です。 文字列内の各インデックスから、可能な限り両側を拡張しようとします。

素朴なアプローチの実装を見てみましょう。

文字列内のすべての可能なインデックスを繰り返し処理します。 インデックスごとに、ゼロに設定します。 また、チェックする次の範囲のインデックスにとを設定します。

次に、現在の範囲が回文を形成するかどうかを確認します。 範囲が回文を形成し、次の範囲に移動した場合、つまり; indexと。の文字をチェックするだけで済みます。

現在の範囲が回文を形成する場合、1つ増加します。 また、範囲を左右に1つずつ拡張します。

その後、同様の操作を実行して配列を計算します。 違いは、との初期値に注意を払うことです。 その理由は、偶数の長さの回文では、回文のサブストリングの左側にある最後の文字のインデックスであるためです。 残りは、配列の計算に似ています。

最後に、計算された配列と配列を返します。

素朴なアプローチの複雑さはです。ここで、は文字列の長さです。

4. マナチャーのアルゴリズム

Manacherのアルゴリズムは、単純なアプローチと同様の方法で配列と配列を計算します。 ただし、可能であれば、すべての可能な範囲を最初からチェックするのではなく、すでに計算された値を使用しようとします。

まず、一般的な考え方を説明しましょう。 その後、実装と複雑さについて話し合うことができます。

4.1. 一般的なアイデア

次の例を見て、奇数の長さのパリンドロームの概念をよりよく説明しましょう。

インデックス0から7までのすべての値を計算し、を計算する必要があるとします。

を計算する前に、これまでのところ、可能な限り右端で終了する回文サブストリングを保持します。 右端の範囲を選択する理由については、セクション4.4で説明します。 この例では、それは部分文字列です。 したがって、および。

ここで、を計算するために、単純なアプローチに従うことができます。 ただし、すでに計算された値を使用して、比較の数を減らすことができます。

部分文字列が回文であることがわかっているので、範囲の中心に基づいてインデックスの鏡像を計算できます。 この例では、中心はインデックス6です。 したがって、のミラーはです。

左側は右側の鏡像なので、と言うかもしれません。

ただし、考慮すべき2つのケースがあります。 最初のケースは、与えられた例に似ています。 の値を超えて拡張できます。 したがって、の値を確認せずに、2から拡張して先に進むことができます。 この例では、を取得します。

2番目のケースは、2番目の例で示されています。

この場合、はとは言えません。これは、との範囲外にある範囲に対応しているためです。

したがって、は、の範囲に含まれる最大範囲であるため、の値しか確認できません。 その後、素朴なアプローチに従って範囲を拡大することができます。 この例では、範囲を拡張できなくなりました。

4.2. 奇数長のパリンドロームのアルゴリズム

一般的な考え方を理解したので、実装を確認できます。 奇数の長さのパリンドロームに対するManacherのアルゴリズムの実装を見てください。

最初は、ゼロとで初期化し、空の範囲を示します。 次に、文字列を左から右に繰り返します。

インデックスごとに、ナイーブアプローチのデフォルト値であるゼロに初期化します。 ここで、すでに計算された値を使用しようとします。

が範囲内にある場合、の値を更新して、そのミラーインデックスの値にします。 ただし、ミラーインデックスの結果が範囲外になる場合に注意します。

したがって、ミラーインデックスの最小値と、現在の回文範囲から取得できる最大長の間になります。

はのミラーインデックスなので、が。よりも小さいかどうかを確認するだけで十分です。 その理由は、に等しいということです。ここで、はのミラーインデックスです。 したがって、それらのいずれかがミラーインデックスよりも小さいかどうかを確認するだけで十分です。

初期値をに割り当てたら、単純なアプローチに従い、インデックスを中心とする範囲を可能な限り拡大しようとします。 ただし、この場合はからから始めます。

その後、との値を更新する必要があるかどうかを確認します。 可能な限り右に行く回文範囲を保存する必要があるため、現在の範囲が保存された範囲よりも右にあるかどうかを確認します。 その場合、との値を更新します。

最後に、計算されたの配列を返します。

4.3. 偶数長のパリンドロームのアルゴリズム

偶数の長さのパリンドロームのアルゴリズムは、奇数の長さのパリンドロームのアルゴリズムに少し変更が加えられています。 その実装を見てください：

このアルゴリズムは、アルゴリズム2に似ています。 ただし、との初期値を変更して、チェックする次の範囲に合わせます。 その理由は、偶数の長さのパリンドロームには2つの中心インデックスがあるためです。 私たちの実装では、は2つの中央のインデックスの間の左側のインデックスです。

その後、パリンドロームの範囲を可能な限り拡大しようとします。常にゼロから開始するのではなく、の値から比較を開始するように注意します。

終了したら、現在保存されている右端の範囲を更新します。

最後に、計算されたの配列を返します。

4.4. コンセプトの証明

まず、右端の回文部分文字列を常に手元に置いておくことが最適であることを証明しましょう。 右側が小さい範囲を維持するとします。 ただし、それはより広い範囲であり、その開始は保存された範囲よりも左側にあります。

この場合、またはのいずれかを計算するときに考慮する値を最小化します。 したがって、またはの初期値が小さくなる可能性があります。 その結果、想定よりも多くの比較を実行することになります。

このことから、右端の範囲を維持することが常に最適であると結論付けることができます。

それでは、複雑さについて説明しましょう。

4.5. 複雑

一見すると、複雑さは素朴なアプローチに似ていると思うかもしれません。 ただし、詳しく調べると、毎回、からまたはから開始することがわかります。

が、より小さい場合、範囲はそれ以上拡張されません。 その理由は、範囲が拡張された場合、範囲の両側が互いにミラーであるため、値が大きくなるためです。

したがって、この場合、比較は成功しません。

それ以外の場合、が、よりも小さい場合は、比較が成功する可能性があります。 ただし、この場合、現在の範囲よりも右側にある回文範囲を調査します。 したがって、比較が成功するたびに、後で右に移動します。

その結果、比較操作が成功するたびに、前進するためのワンステップの動きも生じます。 また、決して減らされないことに気付くことができます。

したがって、内部のwhileループはほとんどの場合実行されます。 したがって、 Manacherのアルゴリズムの複雑さはです。ここで、は文字列内の文字数です。

5. アプリケーション

Manacherのアルゴリズムを使用できるいくつかのアプリケーションを調べてみましょう。

5.1. 最長の回文部分文字列

問題が文字列を与え、文字列内の最長の回文部分文字列を計算するように要求するとします。

これは、Manacherのアルゴリズムの簡単なアプリケーションです。 アルゴリズム2と3に示すように、両方の配列を計算するだけです。

これらの配列は各インデックスの最長のパリンドロームサブストリングを格納するため、値とを確認するだけで済みます。 これらすべての値から、答えはそれらの中で可能な限り最大です。

説明されているアプローチの時間計算量はです。ここで、は文字列の長さです。

5.2. 回文サブストリングの数

別のアプリケーションは、特定の文字列内の回文サブ文字列の数を計算することです。

同様に、アルゴリズム2と3に示すように、両方の配列を計算します。 その後、これら2つの配列のすべての可能な値を繰り返し処理します。

配列には、最長の回文サブストリングの各辺の長さが格納されます。 これらの各サブストリングの最初と最後の文字を削除することにより、新しい回文を取得します。

したがって、次のように計算する必要があります。

   

インデックスごとに1つ追加して、すべての文字が独自の回文であることを示していることに注意してください。

さらに、以下を計算する必要があります。

   

最後に、の値を返す必要があります。

説明されているソリューションは、時間計算量で実装できます。ここで、は文字列の長さです。

5.3. 異なる回文サブストリングの数

この問題は前の問題と似ています。 ただし、一般に回文の部分文字列の数を計算する代わりに、さまざまな回文の部分文字列の数を計算するように求められます。 したがって、2つ以上の等しい部分文字列が回文である場合、回答は1つだけインクリメントする必要があります。

この問題は少し注意が必要で、Manacherのアルゴリズムをよく理解する必要があります。

まず、インデックスのミラーのLPS値を取得すると、この値はインデックスのサブストリングとまったく同じサブストリングに対応します。 この値は、ミラーインデックスにあるときにすでに計算されているため、計算する必要はありません。

ただし、各拡張操作により、新しい異なるサブストリングが生成される場合があります。 ほとんどの場合、拡張操作が実行されることに注意してください。

Rabin-Karpアルゴリズムで使用されるものと同様のハッシュ関数を使用できます。 ハッシュ関数は、一定の時間計算量で特定の部分文字列のハッシュ値を提供できます。 したがって、線形時間での展開演算から生じるすべてのサブストリングのハッシュ値を計算できます。

最後に、答えは、繰り返されない結果のハッシュ値の数です。 これを行うには、すべてのハッシュ値をhash-setに挿入します。 次に、同じ値を1回だけ追加するため、答えはハッシュセットのサイズになります。

このアプローチは、時間計算量で効率的に実装できます。ここで、は文字列の長さです。

6. 結論

このチュートリアルでは、パリンドロームという用語について説明し、特定の文字列内のパリンドロームのサブストリングについて説明しました。

まず、素朴なアプローチについて説明しました。

その後、奇数長と偶数長のパリンドロームを取得する両方のバージョンでManacherのアルゴリズムを説明しました。

最後に、線形時間計算量でManacherのアルゴリズムを使用して解決できるいくつかの問題を提示しました。