Проверка, является ли строка повторяющейся подстрокой

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 .