Python の最長共通部分列
Rohan Timalsina
2023年10月10日
サブシーケンスは、残りの文字の順序を変更せずに一部またはまったく文字を削除した後に、指定されたシーケンスから取得されたシーケンスです。 最長の共通部分列とは、与えられたすべての列に共通する最長の部分列を意味します。
このチュートリアルでは、Python で 2つのシーケンス間の最長の共通部分シーケンスの長さを見つける方法を説明します。
単純な方法を使用して Python で最長共通部分列を見つける
S1 と S2 の 2つのシーケンスがあるとします。
S1 = QEREW
S2 = QWRE
ここで、一般的なサブシーケンスは、QE、QW、QR、QRE、および RE です。 これらのうち、最も長い共通部分列は QRE で、その長さは 3 です。
では、最長共通部分列の長さを出力する Python ソリューションを見てみましょう。
コード：
def LCS(S1, S2, x, y):
if x == 0 or y == 0:
return 0
if S1[x - 1] == S2[y - 1]:
return LCS(S1, S2, x - 1, y - 1) + 1
return max(LCS(S1, S2, x, y - 1), LCS(S1, S2, x - 1, y))
S1 = "QEREW"
S2 = "QWRE"
x = len(S1)
y = len(S2)
print("Length of LCS is", LCS(S1, S2, x, y))
出力：
Length of LCS is 3
この方法は、Python で LCS 問題を解決するための再帰的なアプローチです。 指定されたシーケンスのすべての可能なサブシーケンスをチェックし、最長の共通サブシーケンスを見つけます。
動的計画法を使用して Python で最長共通部分列を見つける
動的計画法は単純な再帰法の最適化です。 ご覧のとおり、再帰的アプローチには重複するサブ問題があり、多くの関数呼び出しが繰り返されています。
動的アプローチでは、各関数呼び出しの結果が配列に保存されるため、必要なときに使用できます。 その結果、関数呼び出しの数が減ります。
コード：
def LCS(S1, S2, m, n):
R = [[None] * (n + 1) for i in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0 or j == 0:
R[i][j] = 0
elif S1[i - 1] == S2[j - 1]:
R[i][j] = R[i - 1][j - 1] + 1
else:
R[i][j] = max(R[i - 1][j], R[i][j - 1])
return R[m][n]
S1 = "QEREW"
S2 = "QWRE"
m = len(S1)
n = len(S2)
print("Length of LCS is", LCS(S1, S2, m, n))
出力：
Length of LCS is 3
この方法は、時間計算量が O(mn) であるため、より高速で効率的です。
著者： Rohan Timalsina
