Substring de palíndromo mais longo em uma string em Java

Subsequência Palíndroma Mais Longa em uma String em Java

Introdução

Em ciência da computação, uma string palíndroma é uma sequência de caracteres que, quando lida da esquerda para a direita ou da direita para a esquerda, permanece a mesma. Encontrar a subpalavra palíndroma mais longa em uma string é um problema clássico que testa a eficiência e a compreensão de algoritmos de processamento de strings.

Neste artigo, exploraremos várias abordagens para identificar e extrair a subpalavra palíndroma mais longa em uma string usando a linguagem de programação Java. Abordaremos métodos eficientes e concisos que demonstram os recursos linguísticos e aprimoram as habilidades de resolução de problemas.

Algoritmo de Força Bruta

O algoritmo de força bruta examina todas as subsequências possíveis na string e verifica se cada subsequência é palíndroma. Isso é realizado gerando todas as combinações de índices de início e fim e verificando se a substring resultante é palíndroma. Embora seja simples de entender, esse algoritmo tem complexidade de tempo O(n³), onde n é o comprimento da string, tornando-o impraticável para strings grandes.

Implementação em Java

java
public static String longestPalindromeBruteForce(String str) {
int n = str.length();
String longestPalindrome = "";

for (int i = 0; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
String substring = str.substring(i, j);
if (isPalindrome(substring) && substring.length() > longestPalindrome.length()) {
longestPalindrome = substring;
}
}
}

return longestPalindrome;
}

private 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;
}


Algoritmo de Programação Dinâmica

O algoritmo de programação dinâmica constrói uma tabela que armazena se as subsequências de um determinado intervalo de índices formam palíndromos. Ele começa preenchendo a tabela com valores true para subsequências de comprimento 1 e, em seguida, processa subsequências maiores, verificando se os caracteres nas extremidades são iguais e se a subpalavra entre elas é um palíndromo.

Implementação em Java

java
public static String longestPalindromeDP(String str) {
int n = str.length();
boolean[][] dp = new boolean[n][n];

String longestPalindrome = "";
int longestLength = 0;

// Preencher a tabela com valores true para subsequências de comprimento 1
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}

// Processar subsequências maiores
for (int l = 2; l <= n; l++) {
for (int i = 0; i <= n - l; i++) {
int j = i + l - 1;

if (str.charAt(i) == str.charAt(j) && (l == 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;

if (l > longestLength) {
longestLength = l;
longestPalindrome = str.substring(i, j + 1);
}
}
}
}

return longestPalindrome;
}


Algoritmo Manacher

O algoritmo Manacher, também conhecido como algoritmo de expansão central, é um método linear eficiente para encontrar a subpalavra palíndroma mais longa. Ele cria um array que representa o raio de expansão máxima de cada caractere na string, considerando tanto palíndromos ímpares quanto pares.

Implementação em Java

java
public static String longestPalindromeManacher(String str) {
int n = str.length();
int[] p = new int[n];

int center = 0;
int right = 0;
int maxLen = 0;
String longestPalindrome = "";

for (int i = 0; i < n; i++) {
// Verificar se o caractere atual está dentro do intervalo de expansão central
int mirror = 2 * center - i;
if (right > i) {
p[i] = Math.min(right - i, p[mirror]);
}

// Expandir o palíndromo ao redor do caractere atual
while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n && str.charAt(i - p[i] - 1) == str.charAt(i + p[i] + 1)) {
p[i]++;
}

// Atualizar o intervalo de expansão central
if (i + p[i] > right) {
center = i;
right = i + p[i];
}

// Atualizar o palíndromo mais longo
if (p[i] > maxLen) {
maxLen = p[i];
longestPalindrome = str.substring(i - maxLen, i + maxLen + 1);
}
}

return longestPalindrome;
}


Conclusão

Encontrar a subpalavra palíndroma mais longa em uma string é um problema clássico com várias aplicações práticas. Abordamos três algoritmos eficientes para resolver esse problema: força bruta, programação dinâmica e Manacher.

O algoritmo de força bruta é simples, mas ineficiente para strings grandes. O algoritmo de programação dinâmica oferece uma solução mais eficiente, construindo uma tabela de informações sobre palíndromos. O algoritmo Manacher é o método mais eficiente, usando uma abordagem de expansão central.

A escolha do algoritmo depende do tamanho da string e dos requisitos de desempenho. Para strings pequenas, o algoritmo de força bruta pode ser suficiente. Para strings maiores, a programação dinâmica ou o algoritmo Manacher são opções mais adequadas, com o algoritmo Manacher oferecendo o melhor desempenho.

Perguntas Frequentes

1. Qual é a complexidade de tempo do algoritmo de força bruta?
– O(n³)

2. Qual é a complexidade de tempo do algoritmo de programação dinâmica?
– O(n²)

3. Qual é a complexidade de tempo do algoritmo Manacher?
– O(n)

4. Qual é o melhor algoritmo para encontrar a subpalavra palíndroma mais longa em uma string grande?
– Algorit