文字列の周期性を確認する方法
1. 序章
このチュートリアルでは、文字列の周期性を確認する3つの方法を紹介します。 つまり、サブストリングの1つの繰り返しであるかどうかを確認します。
2. 問題文
文字列（）があり、適切なプレフィックスの1つをそれ自体に複数回連結することで取得できるかどうかを確認したい。 getに繰り返し連結するサブストリングは、そのプレフィックスである必要があります。 そうしないと、文字列全体を形成することができません。
たとえば、の場合、それ自体に2回連結することで取得します。
これを。と書きます。 は接頭辞ではないため、そこから取得することはできません。
したがって、正式には、検索するプレフィックスはの形式になります。
それをどのように決定できるか見てみましょう。
3. ブルートフォースアプローチ
のプレフィックスを繰り返し処理し、それらを連結してが得られるかどうかを確認できます。 に連結するかどうかをテストするために、繰り返し処理して、すべてのをチェックします。 このように、私たちは周期的に繰り返します：
テストが失敗したを見つけた場合は、反復を停止できます。 それ以外の場合は、ある整数に対してそれを証明したので、戻ります。
擬似コードは次のとおりです。
3.1. 複雑
このアルゴリズムの最悪の場合の時間計算量はです。 これが理由です。 最悪の場合の入力は、の形式の文字列です。 このような入力が与えられた場合、アルゴリズムは外側のループごとにシンボル等価性テストを実行します。 したがって、チェックの総数はです。
、、、、の不要なチェックをスキップして、内側のループからチェックを開始した場合でも、複雑さは2次のままになります。
このアプローチの問題は、を形成できないと事前に結論付けることができるプレフィックスからも取得しようとすることです。 重要なのは、がの繰り返しになるために、余りなしで分割する必要があることを観察することです。 たとえば、および。 前者から後者を取得しようとしなくても、それは不可能な作業であると言えます。
4. 改善されたアルゴリズム
したがって、前と同じように外側のループから開始しますが、の約数でない限りテストしません。
反復はで停止できます。これは、を除いて除算よりも大きい数はなく、厳密に次よりも小さくする必要があるためです。
擬似コードは次のとおりです。
もう1つの方法は、の除数を事前に識別して、不要なチェックをスキップすることです。
4.1. 複雑さ
このアプローチの最悪の場合の複雑さを導き出しましょう。 最悪の場合の入力は、前のアルゴリズム（）と同じ形式です。 内部ループの反復は引き続きチェックを実行しますが、の場合にのみ内部ループに入るので、内部ループの数はではなく、に等しくなります。ここで、はの異なる除数の数です。
以来、全体の複雑さはであるため、アルゴリズムは間違いなく2次方程式以下です。 result を使用すると、より厳密な境界を取得できます。
そこから、、つまりアルゴリズムの複雑さはであると結論付けます。
つまり、アルゴリズムの最悪の場合のパフォーマンスは、よりも優れていますが、より劣っています。 その間に問題を解決する方法はありますか？
5. 回転アルゴリズム
文字列の理論を使用して、線形時間アルゴリズムを設計できます。
5.1. 回転定理
文字列は、それ自体の自明でない回転である場合に限り、そのサブ文字列の1つの繰り返しであるという定理を使用します。 それを証明しましょう。
ある長さの場合、最初の記号を削除し、それらをinの最後の出現箇所に追加することにより、同じ文字列を取得します。
他の方向の定理を証明するために、それはそれ自体の自明でない回転であると仮定します。 つまり、最初の記号を削除し、残りの記号に同じ順序で追加して、開始文字列を取得できるようなものがあります。
LHSとRHSは等しいので、、、、、を保持する必要があります。 したがって、次のことを証明しました。
ただし、の回転はに等しいので、記号で再度回転して同じ文字列を取得し、、、、、、、、、と結論付けることができます。 アプローチに従うと、それが得られます。
5.2. アルゴリズム
（時間内に構築可能な）のサブ文字列インデックスを使用する効率的な文字列照合アルゴリズムを使用して、時間内の重要な発生を探すことができます。 したがって、線形最悪の場合の時間で元の問題を解決できます。
6. 結論
この記事では、文字列の周期性をチェックするための3つのアルゴリズムを紹介しました。 1番目と2番目のアルゴリズムは、3番目のアルゴリズムよりも理解と実装が簡単です。 ただし、回転アルゴリズムの方が効率的です。 その最悪の場合の複雑さはですが、他の2つは超線形の時間計算量を持っています。
