文字列が繰り返される部分文字列であるかどうかの確認
1. 序章
このチュートリアルでは、文字列が繰り返されるサブ文字列のシーケンスであるかどうかをJavaでチェックインする方法を示します。
2. 問題
実装を続行する前に、いくつかの条件を設定しましょう。 まず、Stringに少なくとも2文字あると仮定します。
次に、部分文字列が少なくとも1回繰り返されます。
これは、いくつかの繰り返される部分文字列をチェックすることによって、いくつかの例で最もよく示されています。
"aa"
"ababab"
"barrybarrybarry"
そして、いくつかの繰り返されないもの:
"aba"
"cbacbac"
"carlosxcarlosy"
ここで、問題のいくつかの解決策を示します。
3. 素朴なソリューション
最初のソリューションを実装しましょう。
プロセスはかなり単純です。Stringの長さを確認し、最初の1文字の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を作成しましょう。
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. 効率的なソリューション
次に、別のアプローチを説明します。
つまり、文字列は、それ自体が自明でない回転である場合にのみ、繰り返されるサブ文字列で構成されているという事実を利用する必要があります。
ここでの回転とは、S tring の先頭からいくつかの文字を削除し、それらを最後に配置することを意味します。 たとえば、「eldungba」は「baeldung」のローテーションです。 String を回転させて元の文字列を取得すると、この回転を何度も適用して、繰り返されるサブ文字列で構成されるStringを取得できます。
次に、これがこの例の場合であるかどうかを確認する必要があります。 これを達成するために、次のような定理を利用します。
String Aは常にAAのサブストリングであることがわかっているので、 StringAが最初の文字を除くAAのサブストリングであるかどうかを確認するだけで済みます。
public static boolean containsOnlySubstringsEfficient(String string) {
return ((string + string).indexOf(string, 1) != string.length());
}
このメソッドは、前のメソッドと同じ方法でテストできます。 今回は、 O(n)の時間計算量があります。
文字列分析研究で、このトピックに関するいくつかの有用な定理を見つけることができます。
5. 結論
この記事では、StringがJavaのサブ文字列のみで構成されているかどうかを確認する2つの方法を説明しました。
この記事で使用されているすべてのコードサンプルは、GitHubでから入手できます。