Python で最も長い共通の部分文字列
- Python で最も長い共通の部分文字列
- Python でループを使用する最長の一般的な部分文字列
- 再帰を使用して最長の共通部分文字列を見つける
- Python で動的計画法を使用して最長の共通部分文字列を見つける
- まとめ
Python の文字列は、文字のシーケンスを格納して、さまざまな操作を実行します。サブストリングはこれらのストリングの一部です。
この記事では、2つの指定された文字列の間で最も長い共通の部分文字列を見つける必要があり、同じためのさまざまな解決策について説明します。
Python で最も長い共通の部分文字列
サブストリングは、特定のストリング内の文字の連続したシーケンスです。任意の長さにすることができます。
主な問題は、2つの文字列が提供されていることです。指定された文字列間で共通であり、考えられるすべての共通の部分文字列の中で最も長い部分文字列を見つける必要があります。
Input: str1 = "HaveAAppleRegularly"
str2 = "HaveAnAnApple"
Output: "Apple"
上記の例では、指定された文字列の間に 2つの一般的なサブ文字列、"Have"と"Apple"があります。ただし、"Apple"サブストリングの長さは、残りのサブストリングの中で最も長いためです。したがって、結果として表示されます。
この問題は、再帰や動的計画法などのさまざまな概念を使用して解決できます。
Python でループを使用する最長の一般的な部分文字列
ループを使用して、文字列を反復処理できます。ここでループを使用して文字列を反復処理し、指定された 2つの文字列の間で最も長い共通のサブ文字列を見つけることができます。
このアプローチでは、for ループと while ループの両方を使用します。以下は、Python で最も長い一般的なサブストリングを見つけるために従う必要のある手順です。
-
最初の文字列のすべてのサブ文字列を検索します。
-
最初の文字列の現在の部分文字列が 2 番目の文字列の部分文字列でもあることを確認します。
-
両方の部分文字列が一致する場合、それらの長さを特定の変数に格納し、この変数を更新し続けます。
-
最後に、部分文字列の長さを格納する変数には、目的の結果が含まれ、出力されます。
コード例：
str1 = "PokemonGo"
str2 = "StopPokemonLetsGo"
result = 0
for i in range(len(str1)):
for j in range(len(str2)):
k = 0
while (
(i + k) < len(str1) and (j + k) < len(str2) and str1[i + k] == str2[j + k]
):
k = k + 1
result = max(result, k)
print("Length of the longest common substring is:", result)
出力：
Length of the longest common substring is: 7
文字列のすべての部分文字列は O(n^2) 時間で計算できますが、現在の部分文字列が 2 番目の文字列の部分文字列と一致するかどうかを確認するには、O(m) 時間がかかります。上記のアプローチの時間計算量は、O(n^2 * m) になります。ここで、n と m は、それぞれ 2つの指定された文字列の長さです。
ただし、ソリューションを実現するために余分なスペースを使用していないため、上記のソリューションのスペースの複雑さは O(1) になります。
再帰を使用して最長の共通部分文字列を見つける
再帰とは、それ自体を呼び出す関数を指します。再帰的に目前の問題のベースケースと選択図が必要です。
以下の手順に従って、Python で最も長い一般的な部分文字列を見つけます。
-
最長の共通部分文字列を見つけるという与えられた問題では、可能な最小の入力は長さ
0の文字列である可能性があります。したがって、基本ケースでは、入力の長さのいずれかが0であるかどうかをチェックし、関数は0を返す必要があります。 -
ここで、両方の文字列の最後の文字を比較します。次に、両方の文字が一致する場合と一致しない場合の 2つのケースが発生します。
-
指定された各文字列の最後の文字が一致する場合、残りの文字列を再帰的に呼び出す必要があります。したがって、両方の文字列の長さを
1減らし、それに 1 を追加して、文字列の長さをカウントします。 -
ただし、文字が一致しない場合は、最初の文字列を呼び出して長さを
1デクリメントし、次に 2 番目の文字列を呼び出して長さを1デクリメントします。 -
2つの呼び出し間の最大値である長さが、結果に使用されます。
コード例：
def LCS(s1, s2, n, m):
if n == 0 or m == 0:
return 0
if s1[n - 1] == s2[m - 1]:
return 1 + lcs(s1, s2, n - 1, m - 1)
else:
return max(lcs(s1, s2, n, m - 1), lcs(s1, s2, n - 1, m))
s1 = "pokemonGo"
s2 = "watchPokemon"
n = len(s1)
m = len(s2)
res = lcs(s1, s2, n, m)
print("Length of the longest common substring is:", res)
出力：
Length of the longest common substring is: 7
上記のソリューションの時間計算量は O(3^(m+n)) になり、空間計算量は O(m+n) になります。
Python で動的計画法を使用して最長の共通部分文字列を見つける
動的計画法の基本的な考え方は、両方の文字列のすべての部分文字列の長さを見つけて、それぞれの長さをテーブルに格納することです。再帰を使用しているため、入力が大きい場合、再帰スタックが増加し続けるため、スタックオーバーフローエラーが発生する可能性があります。
テーブルを形成し、それぞれの部分文字列の結果を格納し続ける動的計画法の概念を紹介します。再帰で使用したのと同じアルゴリズムが、いくつかの変更を加えて使用されています。
次に、Python で最も長い共通の部分文字列を見つける手順について説明します。
-
まず、テーブルの最初の列と最初の行を初期化します。これらのセルは、再帰の基本条件で見たように、
0の値で初期化されます。 -
ロジックの再帰呼び出しの代わりにループを使用します。
-
ループ内で、両方の文字列の最後の文字が一致する場合、特定のセルの長さを
1増やします。 -
それ以外の場合は、特定のセルの隣接する行と列までの最大長を格納します。
-
最後に、結果はテーブルの最後の位置に保存されます。したがって、
dp[m][n]を返します。
コード例：
def LCS(X, Y, m, n):
dp = [[0 for x in range(m + 1)] for y in range(n + 1)]
for i in range(m + 1):
for j in range(n + 1):
if X[i - 1] == Y[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
s1 = "playbatball"
s2 = "batballwicket"
n = len(s1)
m = len(s2)
res = lcs(s1, s2, n, m)
print("Length of the longest common substring is:", res)
出力：
Length of the longest common substring is: 7
このソリューションにはループが 2つしかないため、上記のソリューションの時間計算量は O(m*n) になります。結果を保存するためのテーブルを作成することにより、余分なスペースを使用しています。
上記のソリューションのスペースの複雑さは、O(m*n) になります。
まとめ
与えられた 2つの文字列の間で最も長い共通の部分文字列を見つけるための 3つの異なるアプローチを学びました。最初のアプローチである単純なアプローチは、3つのループを使用して、指定された文字列のすべてのサブストリングを検索し、すべてのサブストリングの中で最も長いものをチェックし続けます。
2 番目のアプローチは再帰を使用しますが、3 番目のアプローチは動的計画法を使用して Python で最も長い共通の部分文字列を見つけます。3 番目のアプローチは、この記事で説明したすべてのソリューションの中で問題を解決するための最速であり、推奨されるはずです。