1. Przegląd
W tym krótkim samouczku omówimy różne podejścia do znajdowania wszystkich podciągów w danym ciągu, które są palindromami . Zwrócimy również uwagę na złożoność czasową każdego podejścia.
2. Podejście siłowe
W tym podejściu po prostu iterujemy po ciągu wejściowym, aby znaleźć wszystkie podciągi. Jednocześnie sprawdzimy, czy podciąg jest palindromem, czy nie:
public Set findAllPalindromesUsingBruteForceApproach(String input) { Set 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; }W powyższym przykładzie porównujemy podciąg z jego odwrotnością, aby sprawdzić, czy jest to palindrom:
private boolean isPalindrome(String input) { StringBuilder plain = new StringBuilder(input); StringBuilder reverse = plain.reverse(); return (reverse.toString()).equals(input); }Oczywiście bez problemu możemy wybierać spośród kilku innych podejść.
Złożoność czasowa tego podejścia wynosi O (n ^ 3). Chociaż może to być dopuszczalne w przypadku małych ciągów wejściowych, będziemy potrzebować bardziej wydajnego podejścia, jeśli sprawdzamy palindromy w dużych ilościach tekstu.
3. Podejście centralizacji
Ideą podejścia centralizacyjnego jest rozważenie każdego znaku jako osi obrotu i rozszerzenie w obu kierunkach w celu znalezienia palindromów .
Rozszerzymy tylko wtedy, gdy znaki po lewej i prawej stronie pasują do siebie, kwalifikując ciąg jako palindrom. W przeciwnym razie przechodzimy do następnej postaci.
Zobaczmy szybką demonstrację, w której rozważymy każdy znak jako środek palindromu:
public Set findAllPalindromesUsingCenter(String input) { Set 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; }W powyższej pętli rozszerzamy się w obu kierunkach, aby uzyskać zestaw wszystkich palindromów wyśrodkowanych w każdej pozycji. Znajdziemy palindromy o parzystej i nieparzystej długości, wywołując w pętli metodę findPalindromes :
private Set findPalindromes(String input, int low, int high) { Set 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; }Złożoność czasowa tego podejścia wynosi O (n ^ 2). Jest to ulepszenie w stosunku do naszego podejścia opartego na brutalnej sile, ale możemy zrobić to jeszcze lepiej, jak zobaczymy w następnej sekcji.
4. Algorytm Manachera
Algorytm Manachera znajduje najdłuższy podciąg palindromiczny w czasie liniowym . Użyjemy tego algorytmu do znalezienia wszystkich podciągów, które są palindromami.
Zanim zagłębimy się w algorytm, zainicjujemy kilka zmiennych.
Najpierw będziemy chronić ciąg wejściowy za pomocą znaku granicy na początku i na końcu, zanim skonwertujemy wynikowy ciąg na tablicę znaków:
String formattedInput = "@" + input + "#"; char inputCharArr[] = formattedInput.toCharArray();Następnie użyjemy dwuwymiarowego promienia tablicy z dwoma wierszami - jeden do przechowywania długości palindromów o nieparzystej długości, a drugi do przechowywania długości palindromów o parzystej długości:
int radius[][] = new int[2][input.length() + 1];Następnie wykonamy iterację po tablicy wejściowej, aby znaleźć długość palindromu wyśrodkowanego w pozycji i i zapiszemy tę długość w promieniu [] [] :
Set 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; } }Na koniec przejdziemy przez tablicę promień [] [], aby obliczyć podciągi palindromiczne wyśrodkowane w każdej pozycji:
for (int i = 1; i <= input.length(); i++) { for (int j = 0; j 0; max--) { palindromes.add(input.substring(i - max - 1, max + j + i - 1)); } } }Złożoność czasowa tego podejścia wynosi O (n).
5. Wniosek
W tym krótkim artykule omówiliśmy złożoność czasową różnych podejść do znajdowania podciągów, które są palindromami.
Jak zawsze, pełny kod źródłowy przykładów jest dostępny na GitHub.