Python: Die längste gemeinsame Teilzeichenkette zweier Zeichenketten finden
Das Problem des längsten gemeinsamen Teilstrings bezieht sich darauf, bei zwei gegebenen Strings den längsten gemeinsamen Teilstring zwischen ihnen zu finden. Ein Teilstring ist eine zusammenhängende Zeichenfolge in einem String. Wir können dynamische Programmierung verwenden, um dieses Problem zu lösen.
Beispiel
def longest_common_substring(s1, s2):
m = len(s1)
n = len(s2)
# Erstelle ein zweidimensionales Array, um die Länge der längsten gemeinsamen Teilzeichenkette zu speichern
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_length = 0 # Speichere die Länge der längsten gemeinsamen Teilzeichenkette
end_pos = 0 # Speichere die Endposition der längsten gemeinsamen Teilzeichenkette
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
# Gib die längste gemeinsame Teilzeichenkette zurück
return s1[end_pos - max_length:end_pos]
# Test
s1 = "abcdef"
s2 = "zbcdf"
result = longest_common_substring(s1, s2)
print("Die längste gemeinsame Teilzeichenkette ist:", result)
m = len(s1)
n = len(s2)
# Erstelle ein zweidimensionales Array, um die Länge der längsten gemeinsamen Teilzeichenkette zu speichern
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_length = 0 # Speichere die Länge der längsten gemeinsamen Teilzeichenkette
end_pos = 0 # Speichere die Endposition der längsten gemeinsamen Teilzeichenkette
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
# Gib die längste gemeinsame Teilzeichenkette zurück
return s1[end_pos - max_length:end_pos]
# Test
s1 = "abcdef"
s2 = "zbcdf"
result = longest_common_substring(s1, s2)
print("Die längste gemeinsame Teilzeichenkette ist:", result)
Code-Erklärung:
dpist ein zweidimensionales Array,dp[i][j]repräsentiert die Zeichenkettes1die ersteniZeichen und die Zeichenkettes2die erstenjZeichen der Länge des längsten gemeinsamen Teilstrings.- Wir iterieren durch jedes Zeichen der beiden Strings, wenn
s1[i-1]unds2[j-1]gleich sind, danndp[i][j]der Wert von ... entsprichtdp[i-1][j-1] + 1, andernfallsdp[i][j]ist 0. max_lengthverwendet, um die Länge des längsten gemeinsamen Teilstrings aufzuzeichnen,end_posverwendet, um die Endposition des längsten gemeinsamen Teilstrings aufzuzeichnen.- Schließlich verwenden wir
s1[end_pos - max_length:end_pos]um den längsten gemeinsamen Teilstring zu erhalten.
Ausgabeergebnis:
最长公共子串是: bcdAndere Erweiterungen
Python3-Beispiele