ボトムアップアプローチによる動的計画法を使用して最長の共通部分文字列を見つけるPythonプログラム

ボトムアップアプローチによる動的計画法を使用して最長の共通部分文字列を見つける必要がある場合は、より小さな問題の解を計算するメソッドを定義できます。これらの小さな問題の結果は、何度も計算する必要はありません。代わりに、必要なときにアクセスできます。これは、手元にあるより大きな問題の解決策を開発することにつながります。

以下は同じのデモンストレーションです-

例

def compute_lcw(string_1, string_2):
   val = [[-1]*(len(string_2) + 1) for _ in range(len(string_1) + 1)]
   for i in range(len(string_1) + 1):
      val[i][len(string_2)] = 0
   for j in range(len(string_2)):
      val[len(string_1)][j] = 0
   lcw_i = lcw_j = -1
   lcw_len = 0
   for i in range(len(string_1) - 1, -1, -1):
      for j in range(len(string_2)):
         if string_1[i] != string_2[j]:
            val[i][j] = 0
         else:
            val[i][j] = 1 + val[i + 1][j + 1]
            if lcw_len < val[i][j]:
               lcw_len = val[i][j]
               lcw_i = i
               lcw_j = j
   return lcw_len, lcw_i, lcw_j
string_1 = 'bull'
string_2 = 'bullied'
lcw_len, lcw_i, lcw_j = compute_lcw(string_1, string_2)
print("The longest common substring is : ")
if lcw_len > 0:
   print(string_1[lcw_i:lcw_i + lcw_len])

出力

The longest common substring is :
bull

説明

• 「compute_lcw」という名前のメソッドが定義されています。このメソッドは、パラメーターとして2つの文字列を取ります。
• 2つの文字列が繰り返され、両方に一致する文字列が見つかったかどうかが確認されます。
• 1つの文字が見つかった場合でも、それは別の変数に格納されます。
• これが文字列の最後まで続くと、これらの文字列の両方に別の文字列が共通になります。
• 2つの文字列が定義されており、これら2つの文字列を渡すことでメソッドが呼び出されます。
• この操作のデータは変数に割り当てられます。
• コンソールに出力として表示されます。