«1. Введение

В этом руководстве мы покажем, как мы можем проверить в Java, является ли строка последовательностью повторяющихся подстрок.

2. Проблема

Прежде чем мы продолжим реализацию, давайте установим некоторые условия. Во-первых, предположим, что наша строка имеет как минимум два символа.

Во-вторых, есть хотя бы одно повторение подстроки.

Лучше всего это проиллюстрировать несколькими примерами, проверив несколько повторяющихся подстрок: 

"aa"
"ababab"
"barrybarrybarry"

И несколько неповторяющихся: 

"aba"
"cbacbac"
"carlosxcarlosy"

Сейчас мы покажем несколько решений проблемы.

3. Наивное решение

Давайте реализуем первое решение.

Процесс довольно прост: мы проверим длину строки и исключим односимвольные строки в самом начале.

Затем, поскольку длина подстроки не может быть больше половины длины строки, мы будем перебирать половину строки и создавать подстроку на каждой итерации, добавляя следующий символ к предыдущей подстроке. .

Затем мы удалим эти подстроки из исходной строки и проверим, равна ли длина \»разделенной\» подстроки нулю. Это будет означать, что он состоит только из своих подстрок: 

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 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. Эффективное решение

Теперь мы проиллюстрируем другой подход.

А именно, мы должны использовать тот факт, что String состоит из повторяющихся подстрок тогда и только тогда, когда это нетривиальное вращение самой себя.

Ротация здесь означает, что мы удаляем некоторые символы из начала строки и помещаем их в конец. Например, «eldungba» — это вращение «baeldung». Если мы вращаем строку и получаем исходную, то мы можем применять это вращение снова и снова и получать строку, состоящую из повторяющихся подстрок.

Далее нам нужно проверить, так ли это в нашем примере. Для этого мы воспользуемся теоремой, которая гласит, что если строки A и строки B имеют одинаковую длину, то мы можем сказать, что A является вращением B тогда и только тогда, когда A является подстрокой BB. Если мы вернемся к примеру из предыдущего абзаца, мы сможем подтвердить эту теорему: baeldungbaeldung.

Поскольку мы знаем, что наша строка A всегда будет подстрокой AA, нам нужно только проверить, является ли строка A подстрокой AA, за исключением первого символа: 

public static boolean containsOnlySubstringsEfficient(String string) {
    return ((string + string).indexOf(string, 1) != string.length());
}

Мы можем протестировать этот метод так же, как и предыдущий. На этот раз у нас O(n) временная сложность.

Мы можем найти несколько полезных теорем по этой теме в исследованиях по анализу строк.

5. Заключение

В этой статье мы проиллюстрировали два способа проверки того, состоит ли строка только из своих подстрок в Java.

Все примеры кода, использованные в статье, доступны на GitHub.