1. введение
В этом уроке мы покажем, как мы можем проверить в Java, является ли Строка последовательностью повторяющихся подстрок .
2. Проблема
Прежде чем мы продолжим реализацию, давайте установим некоторые условия. Во-первых, мы предположим, что наша строка | имеет по крайней мере два символа.
Во-вторых, существует по крайней мере одно повторение подстроки.
Это лучше всего проиллюстрировать несколькими примерами, проверив несколько повторяющихся подстрок:
"aa" "ababab" "barrybarrybarry"
И несколько неповторяющихся:
"aba" "cbacbac" "carlosxcarlosy"
Теперь мы покажем несколько решений этой проблемы.
3. Наивное Решение
Давайте реализуем первое решение.
Процесс довольно прост: мы проверим длину String и исключим один символ String s в самом начале.
Затем, поскольку длина подстроки не может быть больше половины длины строки, мы будем перебирать половину строки и создавать подстроку в каждой итерации, добавляя следующий символ к предыдущей подстроке.
Затем мы удалим эти подстроки из исходной строки | и проверим, равна ли длина “очищенной” единицы нулю. Это означало бы, что он состоит только из своих подстрок:
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));
Хотя это решение работает, оно не очень эффективно , так как мы перебираем половину строки и используем метод replaceAll () в каждой итерации.
Очевидно, что это связано с затратами на производительность. Он запустится вовремя O(n^2) .
4. Эффективное Решение
Теперь мы проиллюстрируем другой подход.
А именно, мы должны использовать тот факт, что a String состоит из повторяющихся подстрок тогда и только тогда, когда это нетривиальное вращение самого себя .
Вращение здесь означает, что мы удаляем некоторые символы из начала S tring и помещаем их в конец. Например, “эльдунгба” – это вращение “баельдунга”. Если мы повернем Строку и получим исходную, то мы можем применять это вращение снова и снова и получить Строку , состоящую из повторяющихся подстрок.
Next, we need to check if this is the case with our example. To accomplish this, we’ll make use of the теорема which says that if String and A String B have the same length, then we can say that A is a rotation of B if and only if A is a substring of BB.//If we go with the example from the previous paragraph, we can confirm this теорема: ba eldungba eldung//.
Поскольку мы знаем, что наша Строка A всегда будет подстрокой AA, тогда нам нужно только проверить, является ли строка | A-это подстрока AA, исключающая первый символ:
public static boolean containsOnlySubstringsEfficient(String string) {
return ((string + string).indexOf(string, 1) != string.length());
}Мы можем протестировать этот метод так же, как и предыдущий. На этот раз у нас есть O(n) временная сложность.
Мы можем найти некоторые полезные теоремы по этой теме в String analysis research .
5. Заключение
В этой статье мы проиллюстрировали два способа проверки того, состоит ли строка | только из подстрок в Java.
Все примеры кода, используемые в статье, доступны на GitHub .