«1. Обзор

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

2. Подход грубой силы

В этом подходе мы просто перебираем входную строку, чтобы найти все подстроки. В то же время мы проверим, является ли подстрока палиндромом или нет: 

public Set<String> findAllPalindromesUsingBruteForceApproach(String input) {
    Set<String> palindromes = new HashSet<>();
    for (int i = 0; i < input.length(); i++) {
        for (int j = i + 1; j <= input.length(); j++) {
            if (isPalindrome(input.substring(i, j))) {
                palindromes.add(input.substring(i, j));
            }
        }
    }
    return palindromes;
}

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

private boolean isPalindrome(String input) {
    StringBuilder plain = new StringBuilder(input);
    StringBuilder reverse = plain.reverse();
    return (reverse.toString()).equals(input);
}

Конечно, мы можем легко выбрать один из нескольких других подходов.

Временная сложность этого подхода составляет O(n^3). Хотя это может быть приемлемо для небольших входных строк, нам понадобится более эффективный подход, если мы проверяем палиндромы в больших объемах текста.

3. Подход к централизации

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

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

Давайте посмотрим на быструю демонстрацию, в которой мы будем рассматривать каждый символ как центр палиндрома: 

public Set<String> findAllPalindromesUsingCenter(String input) {
    Set<String> palindromes = new HashSet<>();
    for (int i = 0; i < input.length(); i++) {
        palindromes.addAll(findPalindromes(input, i, i + 1));
        palindromes.addAll(findPalindromes(input, i, i));
    }
    return palindromes;
}

В приведенном выше цикле мы расширяемся в обоих направлениях, чтобы получить набор всех палиндромов с центром в каждой позиции. Мы найдем палиндромы как четной, так и нечетной длины, дважды вызвав метод findPalindromes в цикле: 

private Set<String> findPalindromes(String input, int low, int high) {
    Set<String> result = new HashSet<>();
    while (low >= 0 && high < input.length() && input.charAt(low) == input.charAt(high)) {
        result.add(input.substring(low, high + 1));
        low--;
        high++;
    }
    return result;
}

Временная сложность этого подхода составляет O(n^2). Это улучшение по сравнению с нашим подходом грубой силы, но мы можем сделать еще лучше, как мы увидим в следующем разделе.

4. Алгоритм Манахера

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

Прежде чем мы углубимся в алгоритм, мы инициализируем несколько переменных.

Во-первых, мы защитим входную строку граничным символом в начале и в конце, прежде чем преобразовать полученную строку в массив символов: 

String formattedInput = "@" + input + "#";
char inputCharArr[] = formattedInput.toCharArray();

Затем мы будем использовать двумерный массив radius с две строки — одна для хранения длин палиндромов нечетной длины, а другая для хранения длин палиндромов четной длины: 

int radius[][] = new int[2][input.length() + 1];

Далее мы пройдемся по входному массиву, чтобы найти длину палиндром с центром в позиции i и сохранение этой длины в радиусе[][]: 

Set<String> palindromes = new HashSet<>();
int max;
for (int j = 0; j <= 1; j++) {
    radius[j][0] = max = 0;
    int i = 1;
    while (i <= input.length()) {
        palindromes.add(Character.toString(inputCharArr[i]));
        while (inputCharArr[i - max - 1] == inputCharArr[i + j + max])
            max++;
        radius[j][i] = max;
        int k = 1;
        while ((radius[j][i - k] != max - k) && (k < max)) {
            radius[j][i + k] = Math.min(radius[j][i - k], max - k);
            k++;
        }
        max = Math.max(max - k, 0);
        i += k;
    }
}

Наконец, мы пройдемся по массиву radius[][] для вычисления палиндромных подстрок с центром в каждой позиции: 

for (int i = 1; i <= input.length(); i++) {
    for (int j = 0; j <= 1; j++) {
        for (max = radius[j][i]; max > 0; max--) {
            palindromes.add(input.substring(i - max - 1, max + j + i - 1));
        }
    }
}

~ ~~ Временная сложность этого подхода составляет O(n).

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

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

Как всегда, полный исходный код примеров доступен на GitHub.