Python Trouver la plus longue sous-chaîne commune de deux chaînes
Le problème de la plus longue sous-chaîne commune consiste, étant donné deux chaînes, à trouver la plus longue sous-chaîne commune entre elles. Une sous-chaîne est une séquence contiguë de caractères dans une chaîne. Nous pouvons utiliser la programmation dynamique pour résoudre ce problème.
Exemple
def longest_common_substring(s1, s2):
m = len(s1)
n = len(s2)
# Créer un tableau à deux dimensions pour stocker la longueur de la plus longue sous-chaîne commune
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_length = 0 # Enregistrer la longueur de la plus longue sous-chaîne commune
end_pos = 0 # Enregistrer la position de fin de la plus longue sous-chaîne commune
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
# Retourner la plus longue sous-chaîne commune
return s1[end_pos - max_length:end_pos]
# Test
s1 = "abcdef"
s2 = "zbcdf"
result = longest_common_substring(s1, s2)
print("La plus longue sous-chaîne commune est :", result)
m = len(s1)
n = len(s2)
# Créer un tableau à deux dimensions pour stocker la longueur de la plus longue sous-chaîne commune
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_length = 0 # Enregistrer la longueur de la plus longue sous-chaîne commune
end_pos = 0 # Enregistrer la position de fin de la plus longue sous-chaîne commune
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
# Retourner la plus longue sous-chaîne commune
return s1[end_pos - max_length:end_pos]
# Test
s1 = "abcdef"
s2 = "zbcdf"
result = longest_common_substring(s1, s2)
print("La plus longue sous-chaîne commune est :", result)
Explication du code :
dpest un tableau à deux dimensions,dp[i][j]représente la chaînes1les premiersicaractères et la chaînes2les premiersjcaractères de la longueur de la plus longue sous-chaîne commune.- Nous parcourons chaque caractère des deux chaînes, si
s1[i-1]ets2[j-1]sont égaux, alorsdp[i][j]la valeur de ... est égale àdp[i-1][j-1] + 1, sinondp[i][j]est 0. max_lengthutilisé pour enregistrer la longueur de la plus longue sous-chaîne commune,end_posutilisé pour enregistrer la position de fin de la plus longue sous-chaîne commune.- Enfin, nous utilisons
s1[end_pos - max_length:end_pos]pour obtenir la plus longue sous-chaîne commune.
Résultat de sortie :
最长公共子串是: bcdAutres extensions
Exemples Python3