Python: Die längste gemeinsame Teilzeichenkette zweier Zeichenketten finden

Document 对象参考手册Python3-Beispiele

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)

Code-Erklärung:

  1. dpist ein zweidimensionales Array,dp[i][j]repräsentiert die Zeichenkettes1die ersteniZeichen und die Zeichenkettes2die erstenjZeichen der Länge des längsten gemeinsamen Teilstrings.
  2. Wir iterieren durch jedes Zeichen der beiden Strings, wenns1[i-1]unds2[j-1]gleich sind, danndp[i][j]der Wert von ... entsprichtdp[i-1][j-1] + 1, andernfallsdp[i][j]ist 0.
  3. max_lengthverwendet, um die Länge des längsten gemeinsamen Teilstrings aufzuzeichnen,end_posverwendet, um die Endposition des längsten gemeinsamen Teilstrings aufzuzeichnen.
  4. Schließlich verwenden wirs1[end_pos - max_length:end_pos]um den längsten gemeinsamen Teilstring zu erhalten.

Ausgabeergebnis:

最长公共子串是: bcd

Document 对象参考手册Python3-Beispiele

Andere Erweiterungen