Encontre o Maior Palíndromo em Java: 3 Algoritmos (Força Bruta, PD, Manacher)

No universo da ciência da computação, uma sequência de caracteres que se mantém idêntica quando lida em ambas as direções (da esquerda para a direita ou vice-versa) é denominada palíndroma. A busca pela maior subsequência palíndroma dentro de uma string é um desafio clássico, que avalia a perícia e o entendimento de algoritmos de processamento textual.

Neste artigo, iremos explorar diversas estratégias para identificar e extrair a maior subcadeia palíndroma em strings, utilizando a linguagem de programação Java. Examinaremos abordagens eficazes e diretas, que evidenciam os recursos da linguagem e aprimoram a destreza na solução de problemas.

Estratégia da Força Bruta

A estratégia da força bruta analisa todas as subsequências concebíveis dentro da string, checando se cada uma delas é palíndroma. Isso é feito através da criação de todas as junções possíveis de índices de início e fim, e da verificação se a substring resultante é um palíndromo. Apesar de ser uma abordagem fácil de compreender, este algoritmo possui uma complexidade de tempo de O(n³), onde n representa o tamanho da string, o que o torna inviável para strings extensas.

Implementação em Java

public static String encontrarMaiorPalindromoForcaBruta(String str) {
    int n = str.length();
    String maiorPalindromo = "";

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

    return maiorPalindromo;
}

private static boolean ehPalindromo(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;
}

Abordagem da Programação Dinâmica

O método da programação dinâmica constrói uma tabela que armazena informações sobre se as subsequências em um dado intervalo de índices formam palíndromos. Ele inicia preenchendo a tabela com valores verdadeiros para as subsequências de tamanho 1 e, posteriormente, processa as subsequências mais longas, verificando se os caracteres nas extremidades são idênticos e se a substring entre eles é um palíndromo.

Implementação em Java

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

    String maiorPalindromo = "";
    int maiorTamanho = 0;

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

    // Processa 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 > maiorTamanho) {
                    maiorTamanho = l;
                    maiorPalindromo = str.substring(i, j + 1);
                }
            }
        }
    }

    return maiorPalindromo;
}

O Algoritmo de Manacher

O algoritmo de Manacher, também conhecido como algoritmo de expansão central, é uma estratégia linear eficaz para encontrar a maior subcadeia palíndroma. Ele gera um array que representa o raio de expansão máximo de cada caractere na string, levando em conta tanto palíndromos ímpares quanto pares.

Implementação em Java

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

    int centro = 0;
    int direita = 0;
    int maiorTamanho = 0;
    String maiorPalindromo = "";

    for (int i = 0; i < n; i++) {
        // Verifica se o caractere atual está dentro do alcance da expansão central
        int espelho = 2 * centro - i;
        if (direita > i) {
            p[i] = Math.min(direita - i, p[espelho]);
        }

        // Expande 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]++;
        }

        // Atualiza o alcance da expansão central
        if (i + p[i] > direita) {
            centro = i;
            direita = i + p[i];
        }

        // Atualiza o maior palíndromo encontrado
        if (p[i] > maiorTamanho) {
            maiorTamanho = p[i];
            maiorPalindromo = str.substring(i - maiorTamanho, i + maiorTamanho + 1);
        }
    }

    return maiorPalindromo;
}

Conclusão

A busca pela maior subcadeia palíndroma em uma string é um problema recorrente, com diversas aplicações práticas. Apresentamos três algoritmos eficientes para solucionar este desafio: força bruta, programação dinâmica e Manacher.

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

A escolha do algoritmo correto depende da dimensão da string e das exigências de desempenho. Para strings curtas, o algoritmo de força bruta pode ser suficiente. Para strings maiores, a programação dinâmica ou o algoritmo de Manacher são opções mais adequadas, sendo o algoritmo de Manacher o que oferece 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 de Manacher?	O(n)
4. Qual o melhor algoritmo para encontrar a maior subcadeia palíndroma em uma string grande?	O algoritmo de Manacher.