Python で2つの文字列の最長共通部分文字列を求める
最長共通部分文字列問題とは、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)
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)
コード解析:
dpは二次元配列であり、dp[i][j]は、文字列s1の最初のi文字と文字列s2の最初のj文字の最長共通部分文字列の長さを表します。- 2つの文字列の各文字を走査し、もし
s1[i-1]とs2[j-1]が等しい場合、dp[i][j]の値はdp[i-1][j-1] + 1に等しく、そうでなければdp[i][j]は0です。 max_lengthは最長共通部分文字列の長さを記録するために使用され、end_posは最長共通部分文字列の終了位置を記録するために使用されます。- 最後に、私たちは
s1[end_pos - max_length:end_pos]を用いて最長共通部分文字列を取得します。
出力結果:
最长公共子串是: bcdその他の拡張
Python3 例