Python: Encontrar la subcadena común más larga de dos cadenas
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)
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:
dpes una matriz bidimensional,dp[i][j]representa la cadenas1los primerosicaracteres y la cadenas2los primerosjcaracteres de la subcadena común más larga.- Recorremos cada carácter de las dos cadenas, si
s1[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. 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.- Finalmente, a través de
s1[end_pos - max_length:end_pos]obtenemos la subcadena común más larga.
Resultado de salida:
最长公共子串是: bcdOtras extensiones
Ejemplo de Python3