文字列が繰り返し部分文字列であるかどうかを確認する

1. 前書き

このチュートリアルでは、_String_が繰り返し部分文字列のシーケンスであるかどうかをJavaでチェックする方法を示します。

2. 問題

実装を続ける前に、いくつかの条件を設定しましょう。 最初に、_String_に少なくとも2つの文字があると仮定します。 第二に、部分文字列の少なくとも1つの繰り返しがあります。
これは、いくつかの繰り返し部分文字列をチェックアウトすることにより、いくつかの例で最もよく説明されます。
"aa"
"ababab"
"barrybarrybarry"
そして、いくつかの非繰り返しのもの:
"aba"
"cbacbac"
"carlosxcarlosy"
ここで、問題のいくつかの解決策を示します。

3. 素朴なソリューション

最初のソリューションを実装しましょう。
このプロセスはかなり単純です。_String_の長さをチェックし、最初の1文字の__String__sを削除します。
次に、*部分文字列の長さは文字列の長さの半分を超えることはできないため、* _String_の半分を反復処理し、次の文字を前の部分文字列に追加することで、すべての反復で部分文字列を作成します。
次に、元の_String_からこれらの部分文字列を削除し、「削除」されたものの長さがゼロかどうかを確認します。 これは、サブストリングのみで構成されていることを意味します。
public static boolean containsOnlySubstrings(String string) {

    if (string.length() < 2) {
        return false;
    }

    StringBuilder substr = new StringBuilder();
    for (int i = 0; i < string.length() / 2; i++) {
        substr.append(string.charAt(i));

        String clearedFromSubstrings = string.replaceAll(substr.toString(), "");

        if (clearedFromSubstrings.length() == 0) {
            return true;
        }
    }

    return false;
}
メソッドをテストするために__String__sを作成しましょう:
String validString = "aa";
String validStringTwo = "ababab";
String validStringThree = "baeldungbaeldung";

String invalidString = "aca";
String invalidStringTwo = "ababa";
String invalidStringThree = "baeldungnonrepeatedbaeldung";
そして最後に、その妥当性を簡単に確認できます。
assertTrue(containsOnlySubstrings(validString));
assertTrue(containsOnlySubstrings(validStringTwo));
assertTrue(containsOnlySubstrings(validStringThree));

assertFalse(containsOnlySubstrings(invalidString));
assertFalse(containsOnlySubstrings(invalidStringTwo));
assertFalse(containsOnlySubstrings(invalidStringThree));
このソリューションは機能しますが、_String_の半分を反復処理し、すべての反復で_replaceAll()_メソッドを使用するため、*それはあまり効率的ではありません*。
明らかに、パフォーマンスに関するコストが伴います。 時間内に実行されます_O(n ^ 2)_。

4. 効率的なソリューション

次に、別のアプローチを示します。
すなわち、それがそれ自体の自明でない回転である場合に限り、* a _String_が繰り返し部分文字列で作られているという事実を利用すべきです。
ここでの回転とは、S__tring__の先頭からいくつかの文字を削除し、末尾に配置することを意味します。 たとえば、「eldungba」は「baeldung」の回転です。 _String_を回転させて元のものを取得した場合、この回転を何度も適用して、繰り返し部分文字列で構成される_String_を取得できます。
次に、この例に当てはまるかどうかを確認する必要があります。 これを達成するために、* _ St​​ring_ Aと_String_ Bが同じ長さである場合、AがBBの部分文字列である場合に限り、AがBの回転であると言う定理を利用します。*前の段落の例を使用すると、この定理:_ba ** eldungba ** eldung_を確認できます。
_String_ Aは常にAAの部分文字列であることがわかっているため、_String_ Aが最初の文字を除くAAの部分文字列であるかどうかを確認するだけです。
public static boolean containsOnlySubstringsEfficient(String string) {
    return ((string + string).indexOf(string, 1) != string.length());
}
このメソッドは、前のメソッドと同じ方法でテストできます。 今回は、_O(n)_時間の複雑さがあります。
このトピックに関する有用な定理は、https://www.sciencedirect.com/science/article/pii/S0304397508002880?via%3Dihub [_String_ analysis research]で見つけることができます。

5. 結論

この記事では、_String_がJavaのサブストリングのみで構成されているかどうかを確認する2つの方法を説明しました。
この記事で使用されているすべてのコードサンプルは、https://github.com/eugenp/tutorials/tree/master/java-strings-2 [GitHub上]で入手できます。