1. Введение
В этом уроке мы покажем, как мы можем проверить в Java, является ли строка последовательностью повторяющихся подстрок .
2. Проблема
Прежде чем мы продолжим реализацию, давайте установим некоторые условия. Во-первых, предположим, что наша строка имеет как минимум два символа.
Во-вторых, есть хотя бы одно повторение подстроки.
Лучше всего это проиллюстрировать несколькими примерами, проверив несколько повторяющихся подстрок:
"aa"
"ababab"
"barrybarrybarry"
И несколько неповторяющихся:
"aba"
"cbacbac"
"carlosxcarlosy"
Сейчас мы покажем несколько решений проблемы.
3. Наивное решение
Давайте реализуем первое решение.
Процесс довольно прост: мы проверим длину 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 = "foreachforeach";
String invalidString = "aca";
String invalidStringTwo = "ababa";
String invalidStringThree = "foreachnonrepeatedforeach";
И, наконец, мы можем легко проверить его справедливость:
assertTrue(containsOnlySubstrings(validString));
assertTrue(containsOnlySubstrings(validStringTwo));
assertTrue(containsOnlySubstrings(validStringThree));
assertFalse(containsOnlySubstrings(invalidString));
assertFalse(containsOnlySubstrings(invalidStringTwo));
assertFalse(containsOnlySubstrings(invalidStringThree));
Хотя это решение работает, оно не очень эффективно , поскольку мы перебираем половину строки и используем метод replaceAll() на каждой итерации.
Очевидно, что это связано с затратами на производительность. Это будет работать за время O(n^2) .
4. Эффективное решение
Теперь мы проиллюстрируем другой подход.
А именно, мы должны использовать тот факт, что String состоит из повторяющихся подстрок тогда и только тогда, когда это нетривиальное вращение самой себя .
Ротация здесь означает, что мы удаляем некоторые символы из начала строки S и помещаем их в конец. Например, «eldungba» — это вращение «foreach». Если мы вращаем строку и получаем исходную, то мы можем применять это вращение снова и снова и получать строку , состоящую из повторяющихся подстрок.
Далее нам нужно проверить, так ли это в нашем примере. Для этого мы воспользуемся теоремой, которая гласит, что если строки A и строки B имеют одинаковую длину, то мы можем сказать, что A является вращением B тогда и только тогда, когда A является подстрокой BB. Если мы вернемся к примеру из предыдущего абзаца, мы сможем подтвердить эту теорему: ba eldungba eldung .
Поскольку мы знаем, что наша строка A всегда будет подстрокой AA, нам нужно только проверить, является ли строка A подстрокой AA, за исключением первого символа:
public static boolean containsOnlySubstringsEfficient(String string) {
return ((string + string).indexOf(string, 1) != string.length());
}
Мы можем протестировать этот метод так же, как и предыдущий. На этот раз у нас O(n) временная сложность.
Мы можем найти некоторые полезные теоремы по этой теме в исследованиях по анализу строк .
5. Вывод
В этой статье мы проиллюстрировали два способа проверки того, состоит ли строка только из своих подстрок в Java.
Все примеры кода, использованные в статье, доступны на GitHub .