El problema de encontrar la subcadena común más larga (Longest Common Substring) consiste en identificar la secuencia de caracteres de mayor longitud que aparece de forma idéntica y continua en dos cadenas de texto dadas. A continuación, se presentan dos anfoques comunes para resolver este problema: Programación Dinámica y Fuerza Bruta.

Enfoque 1: Programación Dinámica (Matriz de Coincidencias)

Este método optimiza la búsqueda utilizando una matriz bidimensional para almacenar los resultados de los cálculos intermedios. La lógica se basa en los siguientes puntos:

• Se crea una tabla de dimensiones (n+1) x (m+1), donde n y m son las longitudes de las cadenas.
• Si los caracteres en las posiciones actuales coinciden, el valor de la celda será el valor de la celda diagonal superior izquierda más uno.
• Se mantiene un registro de la longitud máxima encontrada y el índice final para extraer la subcadena al concluir el recorrido.

public String obtenerSubcadenaLCS(String textoA, String textoB) {
    int n = textoA.length();
    int m = textoB.length();
    int[][] matrizDP = new int[n + 1][m + 1];
    int longitudMaxima = 0;
    int posicionFinal = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            // Comparar caracteres (ajustando índice por la matriz desplazada)
            if (textoA.charAt(i - 1) == textoB.charAt(j - 1)) {
                matrizDP[i][j] = matrizDP[i - 1][j - 1] + 1;
                
                if (matrizDP[i][j] > longitudMaxima) {
                    longitudMaxima = matrizDP[i][j];
                    posicionFinal = i;
                }
            } else {
                matrizDP[i][j] = 0;
            }
        }
    }
    
    // Retornar la subcadena utilizando los índices registrados
    return textoA.substring(posicionFinal - longitudMaxima, posicionFinal);
}

Enfoque 2: Búsqueda Exhaustiva (Fuerza Bruta)

Este método es más intuitivo pero menos eficiente para cadenas de gran tamaño. El procedimiento consiste en generar todas las subcadenas posibles de la cadena más corta y verificar si existen dentro de la cadena más larga, priorizando siempre la de mayor longitud.

• Se identifica cuál de las dos entradas es la más corta para reducir el número de iteraciones.
• Mediante bucles anidados, se extraen todos los segmentos posibles.
• Se utiliza el método contains() para validar la presencia del segmento en la cadena secundaria.

public static String buscarSubcadenaFuerzaBruta(String str1, String str2) {
    String fuente = str1.length() < str2.length() ? str1 : str2;
    String objetivo = str1.length() < str2.length() ? str2 : str1;
    
    String subcadenaMasLarga = "";
    int tamanoFuente = fuente.length();

    for (int inicio = 0; inicio < tamanoFuente; inicio++) {
        for (int fin = inicio + 1; fin <= tamanoFuente; fin++) {
            String segmentoActual = fuente.substring(inicio, fin);
            
            // Si el segmento está en el objetivo y es más largo que el actual récord
            if (objetivo.contains(segmentoActual) && segmentoActual.length() > subcadenaMasLarga.length()) {
                subcadenaMasLarga = segmentoActual;
            }
        }
    }
    return subcadenaMasLarga;
}

Mientras que el enfoque de programación dinámica tiene una complejidad temporal de O(n*m), el enfoque de fuerza bruta puede llegar a ser significativamente más costoso debido a la generación de subcadenas y la operación de búsqueda interna, aunque resulta más sencillo de implementar para casos de uso con strings pequeños.