Sottostringa palindroma più lunga in una stringa in Java

di

Sottostringa Palindroma Più Lunga in una Stringa in Java

Introduzione

Una sottostringa palindroma è una sequenza di caratteri che si legge allo stesso modo avanti e indietro, come “radar” o “kayak”. Trovare la sottostringa palindroma più lunga in una data stringa è un problema comune nella programmazione delle stringhe. In questo articolo, esploreremo vari algoritmi per risolvere questo problema in Java.

Algoritmi

1. Algoritmo della Forza Bruta

L’algoritmo della forza bruta genera tutte le possibili sottostringhe della stringa di input e controlla se ciascuna di esse è palindroma. Per verificare se una stringa è palindroma, la si confronta con la sua versione invertita.

java
import java.util.List;
import java.util.ArrayList;

public class Main {

public static void main(String[] args) {
String str = "abbacadd";
List<String> palindromes = new ArrayList<>();

for (int i = 0; i < str.length(); i++) {
for (int j = i + 1; j <= str.length(); j++) {
String substring = str.substring(i, j);
if (isPalindrome(substring)) {
palindromes.add(substring);
}
}
}

String longestPalindrome = null;
for (String palindrome : palindromes) {
if (longestPalindrome == null || palindrome.length() > longestPalindrome.length()) {
longestPalindrome = palindrome;
}
}

System.out.println("La sottostringa palindroma più lunga è: " + longestPalindrome);
}

public static boolean isPalindrome(String str) {
int i = 0;
int j = str.length() - 1;

while (i < j) {
if (str.charAt(i) != str.charAt(j)) {
return false;
}
i++;
j--;
}

return true;
}
}

2. Algoritmo di Manacher

L’algoritmo di Manacher è un algoritmo lineare che costruisce una rappresentazione della stringa di input come una sequenza di caratteri con un carattere speciale inserito tra ogni carattere. Questa rappresentazione consente un controllo efficiente della palindromità.

java
import java.util.List;
import java.util.ArrayList;

public class Main {

public static void main(String[] args) {
String str = "abbacadd";
List<String> palindromes = new ArrayList<>();

// Costruisci la stringa trasformata
String transformedStr = getTransformedString(str);

// Crea il tavolo delle lunghezze palindromiche
int[] p = new int[transformedStr.length()];

// Trova il centro e il raggio della palindroma più lunga corrente
int center = 0;
int radius = 0;

for (int i = 1; i < transformedStr.length(); i++) {
// Controllo del mirroring attorno al centro corrente
int mirror = 2 * center - i;

// Espandi la palindroma fino a quando i caratteri corrispondono o il limite è raggiunto
while (i + radius < transformedStr.length() && i - radius >= 0 &&
transformedStr.charAt(i + radius) == transformedStr.charAt(i - radius)) {
radius++;
}

// Aggiorna il centro e il raggio della palindroma più lunga corrente
if (radius > center) {
center = i;
}

// Salva la palindroma
if (i + radius - 1 - 2 * center >= 0) {
String palindrome = transformedStr.substring(i + radius - 1 - 2 * center, i + radius);
palindromes.add(palindrome.replaceAll("#", ""));
}
}

String longestPalindrome = null;
for (String palindrome : palindromes) {
if (longestPalindrome == null || palindrome.length() > longestPalindrome.length()) {
longestPalindrome = palindrome;
}
}

System.out.println("La sottostringa palindroma più lunga è: " + longestPalindrome);
}

public static String getTransformedString(String str) {
StringBuilder transformedStr = new StringBuilder();

for (char c : str.toCharArray()) {
transformedStr.append("#");
transformedStr.append(c);
}

transformedStr.append("#");

return transformedStr.toString();
}
}

3. Algoritmo di Programmazione Dinamica

L’algoritmo di programmazione dinamica costruisce una matrice che memorizza se le sottostringhe della stringa di input sono palindrome. Utilizzando questa matrice, può determinare efficacemente la sottostringa palindroma più lunga.

java
import java.util.List;
import java.util.ArrayList;

public class Main {

public static void main(String[] args) {
String str = "abbacadd";
List<String> palindromes = new ArrayList<>();

// Costruisci la matrice di palindromicità
boolean[][] dp = new boolean[str.length()][str.length()];

// Inizializza la matrice principale diagonale
for (int i = 0; i < str.length(); i++) {
dp[i][i] = true;
}

// Riempi la matrice diagonale off-principale
for (int i = str.length() - 2; i >= 0; i--) {
for (int j = i + 1; j < str.length(); j++) {
if (str.charAt(i) == str.charAt(j)) {
dp[i][j] = true;
}
}
}

// Riempi la matrice rimanente
for (int k = 2; k < str.length(); k++) {
for (int i = 0; i < str.length() - k; i++) {
int j = i + k;
if (str.charAt(i) == str.charAt(j) && dp[i + 1][j - 1]) {
dp[i][j] = true;
}
}
}

// Trova la sottostringa palindroma più lunga
int end = 0;
int length = 0;

for (int i = 0; i < str.length(); i++) {
for (int j = i; j < str.length(); j++) {
if (dp[i][j] && j - i + 1 > length) {
length = j - i + 1;
end = j;
}
}
}

String longestPalindrome = str.substring(end - length + 1, end + 1);

System.out.println("La sottostringa palindroma più lunga è: " + longestPalindrome);
}
}

Conclusione

La sottostringa palindroma più lunga in una stringa può essere trovata in modo efficiente utilizzando algoritmi di forza bruta, di Manacher o di programmazione dinamica. La scelta dell’algoritmo ottimale dipende dalla lunghezza della stringa di input e dai requisiti di memoria. Per stringhe di piccole e medie dimensioni, l’algoritmo di forza bruta può essere sufficiente. Per stringhe di grandi dimensioni, l’algoritmo di Manacher o di programmazione dinamica offre prestazioni migliori.

FAQs

1. Cos’è una sottostringa palindroma?
Una sottostringa palindroma è una sequenza di caratteri che si legge allo stesso modo avanti e indietro.

2. Perché è importante trovare la sottostringa palindroma più lunga?
Trovare la sottostringa palindroma più lunga ha applicazioni in vari campi, come l’elaborazione del linguaggio naturale e la bioinformatica.

3. Qual è l’algoritmo più efficiente per trovare la sottostringa palindroma più lunga?
L’algoritmo più efficiente dipende dalla lunghezza della stringa di input e dai requisiti di memoria. L’algoritmo di Manacher e quello di programmazione dinamica offrono prestazioni migliori per stringhe di grandi dimensioni.

4. Come posso verificare se una stringa è palindroma?
Puoi verificare se una stringa è palindroma confrontandola con la sua versione invertita.

5. Quali sono alcuni esempi di sottostringhe palindrome?
Esempi di sottostringhe palindrome includono “radar”, “kayak”, “racecar” e “level”.

6. Come posso generare tutte le possibili sottostringhe di una stringa?
Puoi generare tutte le possibili