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 и сохраним эту длину в radius[][] :
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 .