Python で2つの文字列の最長共通部分文字列を求める

Document 对象参考手册Python3 例

最長共通部分文字列問題とは、2つの文字列が与えられたとき、それらの間で最も長い共通部分文字列を見つけることです。部分文字列とは、文字列内の連続する文字の並びを指します。この問題を解決するには、動的計画法を使用できます。

例

def longest_common_substring(s1, s2):
    m = len(s1)
    n = len(s2)
    # 最長共通部分文字列の長さを格納する二次元配列を作成する
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_length = 0  # 最長共通部分文字列の長さを記録する
    end_pos = 0     # 最長共通部分文字列の終了位置を記録する

    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

    # 最長共通部分文字列を返す
    return s1[end_pos - max_length:end_pos]

# テスト
s1 = "abcdef"
s2 = "zbcdf"
result = longest_common_substring(s1, s2)
print("最長共通部分文字列は:", result)

コード解析:

  1. dpは二次元配列であり、dp[i][j]は、文字列s1の最初のi文字と文字列s2の最初のj文字の最長共通部分文字列の長さを表します。
  2. 2つの文字列の各文字を走査し、もしs1[i-1]とs2[j-1]が等しい場合、dp[i][j]の値はdp[i-1][j-1] + 1に等しく、そうでなければdp[i][j]は0です。
  3. max_lengthは最長共通部分文字列の長さを記録するために使用され、end_posは最長共通部分文字列の終了位置を記録するために使用されます。
  4. 最後に、私たちはs1[end_pos - max_length:end_pos]を用いて最長共通部分文字列を取得します。

出力結果:

最长公共子串是: bcd

Document 对象参考手册Python3 例

その他の拡張