Как проверить, имеет ли строка повторяющийся узор?

Question

Мне недавно задали этот вопрос в интервью:

Учитывая, что входная строка проверяет, имеет ли она повторяющийся шаблон, и возвращает true или false. Например: "abbaabbaabbaabba" является повторяющимся шаблоном "abba"

private boolean checkPattern(String input) {

}

Как мы можем решить это с помощью регулярных выражений, а также без регулярных выражений? Меня интересуют оба подхода с регулярным выражением и без регулярного выражения.

Answer 1

Для чего стоит, я нашел решение с помощью регулярных выражений.

Хитрость заключается в том, чтобы использовать обратную ссылку на непустую первую группу.

^(.+)(?:\1)+$

И как @PatrickParkerуказывает, что если вам нужен наименьший повторяющийся паттерн, вы можете использовать ленивый квалификатор

^(.+?)(?:\1)+$

Answer 2

Без регулярного выражения вам пришлось бы перебирать каждую возможную подстроку длины, на которую делится длина исходной строки, начиная с индекса 0, в исходной строке и проверять, повторяется ли она. Чтобы проверить, повторяется ли это, вы просто проверяете каждое pattern.length() количество символов в строке, чтобы увидеть, является ли это шаблоном или нет. Например, это будет выглядеть так:

public boolean checkPattern(String str) {
    String pattern = "";
    for (int i = 0; i < str.length()/2; i++) {
        pattern += str.charAt(i);
        if (str.length() % pattern.length() == 0 && isRepeating(str, pattern)) {
            return true;
        }
    }
    return false;
}

public boolean isRepeating(String str, String pattern) {
    String leftover = str;
    int currIndex = leftover.indexOf(pattern);
    while (currIndex == 0) {
        if(currIndex + pattern.length() == leftover.length()) {
            return true; // you have reached the last possible instance of the pattern at this point
        }
        leftover = leftover.substring(currIndex + pattern.length());
        currIndex = leftover.indexOf(pattern);
    }
    return false;
}

Как и упомянутый пользователь thebjorn, вы можете предотвратить ненужные вызовы isRepeating, вызывая его только тогда, когда длина строки делится на длину шаблона, следовательно, проверка модуля в выражении if. Кроме того, максимальная длина, которую шаблон может повторять в строке, составляет str.length()/2.

Answer 3

Я не знаю RegEx, поэтому я сделаю это по-другому. И это применимо, только если строка не является частичной повторяющейся строкой, то есть "xbcabbaabbaabbaxx"

Сначала вы берете входную строку и находите факторы размера строки. Простое число будет означать, что нет повторяющихся шаблонов, так как повторяющийся шаблон подразумевает кратное по крайней мере 2 длины строки шаблона.

Благодаря Tot Zam: Нахождение коэффициентов для данного целого числа

public ArrayList<Integer> findFactors(int num) {        
    ArrayList<Integer> factors = new ArrayList<Integer>();

    // Skip two if the number is odd
    int incrementer = num % 2 == 0 ? 1 : 2;

    for (int i = 1; i <= Math.sqrt(num); i += incrementer) {

        // If there is no remainder, then the number is a factor.
        if (num % i == 0) {
            factors.add(i);

            // Skip duplicates
            if (i != num / i) {
                factors.add(num / i);
            }

        }
    }

    // Sort the list of factors
    Collections.sort(factors);

    return factors;
}

Как только вы найдете коэффициенты числа, в вашем случае 16 (результат 1,2,4,8,16) и исключая наибольший коэффициент (который сам по себе), вы можете теперь создать цикл и выполнить итерацию подстроки строки. Вы проверяете для каждого значения его предыдущее значение и проверяете, пока не получите правильное значение, используя continue

Например, набросок:

boolean isRepeatingPattern = false;
for (Integer factor : factors) {
    int iterations = stringSize / factor;
    String previousSubstring = stringParam.substring(0, factor); 
    for (int i = 1; i < iterations; i++) {
        int index = i * factor;
        if (previousSubstring != stringParam.substring(index, index + factor)) break;
        if (i == iterations - 1) repeatingPattern = true;
    }
}

Answer 4

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

public static String getRepeatingPattern(String str) {
    String repeatingPattern =null;
    for(int i=0;i<str.length();i++) {
        repeatingPattern = str.substring(0, i+1);
        String[] ary = str.split(repeatingPattern);
        if(ary.length==0) {
            break;
        }
    }
 return repeatingPattern;
}

Answer 5

Создать Trie со всеми подстроками в любом месте. При добавлении, если вы добавляете одно слово дважды, то есть слово, которое было добавлено ранее, это означает, что оно имеет повторяющийся шаблон.

Если вы хотите, чтобы шаблон был длиннее любой длины, измените код, чтобы хранить только слова, длина которых превышает эту длину. Или один символ также может быть повторяющимся шаблоном.

Answer 6

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

Если это соответствует run, если условие для подстроки.

Еслилюбой из предшествующих символов в подстроке не совпадает, выйдите из подстроки, если условие