Python: Encontrar la subcadena común más larga de dos cadenas

Document 对象参考手册Ejemplo de Python3

El problema de la subcadena común más larga consiste en, dadas dos cadenas, encontrar la subcadena común más larga entre ellas. Una subcadena es una secuencia continua de caracteres dentro de una cadena. Podemos usar programación dinámica para resolver este problema.

Ejemplo

def longest_common_substring(s1, s2):
    m = len(s1)
    n = len(s2)
    # Crear una matriz bidimensional para almacenar la longitud de la subcadena común más larga
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_length = 0  # Registrar la longitud de la subcadena común más larga
    end_pos = 0     # Registrar la posición final de la subcadena común más larga

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] > max_length:
                    max_length = dp[i][j]
                    end_pos = i
            else:
                dp[i][j] = 0

    # Devolver la subcadena común más larga
    return s1[end_pos - max_length:end_pos]

# Prueba
s1 = "abcdef"
s2 = "zbcdf"
result = longest_common_substring(s1, s2)
print("La subcadena común más larga es:", result)

Análisis del código:

  1. dpes una matriz bidimensional,dp[i][j]representa la cadenas1los primerosicaracteres y la cadenas2los primerosjcaracteres de la subcadena común más larga.
  2. Recorremos cada carácter de las dos cadenas, sis1[i-1]ys2[j-1]son iguales, entoncesdp[i][j]el valor de es igual adp[i-1][j-1] + 1, de lo contrariodp[i][j]es 0.
  3. max_lengthse utiliza para registrar la longitud de la subcadena común más larga,end_posse utiliza para registrar la posición final de la subcadena común más larga.
  4. Finalmente, a través des1[end_pos - max_length:end_pos]obtenemos la subcadena común más larga.

Resultado de salida:

最长公共子串是: bcd

Document 对象参考手册Ejemplo de Python3

Otras extensiones